Source Code
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

const int MAX = 2e5;

vector<int> pw2 = [](){
  vector<int> ret;
  ret.push_back(1);
  for (int i = 1; i <= MAX; ++i) {
    ret.push_back(ret.back() * 2 % 10);
  }
  return ret;
}();

class SegmentTree {
 private:
  vector<int> tree;
  vector<int> leaves;
  int n;

  inline void pull(int p, int s, int e) {
    int mid = (s + e) / 2;
    tree[p] = (tree[2 * p] * pw2[e - mid] + tree[2 * p + 1]) % 10;
  }

  void build(int p, int s, int e) {
    if (s == e) {
      tree[p] = leaves[s];
      return;
    }
    int mid = (s + e) / 2;
    build(2 * p, s, mid);
    build(2 * p + 1, mid + 1, e);
    pull(p, s, e);
  }

  int query(int p, int s, int e, int l, int r) {
    if (s > r || e < l) {
      return 0;
    }
    if (l <= s && e <= r) {
      return (tree[p] * pw2[r - e]) % 10;
    }
    int mid = (s + e) / 2;
    return (query(2 * p, s, mid, l, r) + query(2 * p + 1, mid + 1, e, l, r)) % 10;
  }

 public:
  SegmentTree(const string &s) {
    n = s.size();
    for (char c : s) {
      leaves.push_back(c - '0');
    }
    tree.resize(4 * n);
    build(1, 0, n - 1);
  }

  int query(int l, int r) {
    return query(1, 0, n - 1, l, r);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  string s;
  cin >> s;
  SegmentTree seg(s);
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l;
    --r;
    int ans = seg.query(l, r);
    cout << ans << '\n';
  }
  return 0;
}
Copy
Binarithm abdulrahman_aj
GNU G++17
312 ms
7.0 MB
Accepted