http://codeforces.com/contest/827/problem/C
e<=10なのでmod eごとにBITを使って処理する。
int n; ll sum(ll *bit, int i) { ll s = 0; while(i > 0) { s += bit[i]; i -= i & -i; } return s; } void add(ll *bit, int i, ll x) { while(i <= n) { bit[i] += x; i += i & -i; } } struct query { int a, b; vector<int> vec; }; ostream& operator<< (ostream& out, const query& v) { out << "(" << v.a << ", " << v.b << ", " << v.vec << ")"; return out; } int N, Q; ll bit[4][11][100010]; int ans[100010]; int S[100010]; query qr[100010]; void show_seg(int m) { rep(i, 0, 4) { rep(j, 0, m) { vector<int> vec; rep(k, 1, n + 1) { vec.push_back(sum(bit[i][j], k)); } debug(i, j, vec); } } } int char_to_int(char c) { if(c == 'A') return 0; if(c == 'T') return 1; if(c == 'G') return 2; if(c == 'C') return 3; return 4; } void solve() { string str; cin >> str; N = str.size(); rep(i, 0, N) S[i] = char_to_int(str[i]); cin >> Q; memset(ans, -1, sizeof(ans)); rep(i, 0, Q) { int t; cin >> t; int a, b; string s; if(t == 1) { cin >> b >> s; b--; a = -1; } else { cin >> a >> b >> s; a--; b--; ans[i] = 0; } vector<int> vec; rep(j, 0, (int)s.size()) vec.push_back(char_to_int(s[j])); qr[i] = (query){a, b, vec}; } rep(m, 1, 11) { memset(bit, 0, sizeof(bit)); n = N / m + 2; vector<int> ts(S, S + N); rep(i, 0, m) { for(int k = 0; i + k * m < N; k++) { int id = i + k * m; add(bit[S[id]][i], k + 1, 1); } } rep(i, 0, Q) { int a = qr[i].a, b = qr[i].b; vector<int> vec = qr[i].vec; if(a == -1) { int t = vec[0]; int pt = ts[b]; add(bit[pt][b % m], b / m + 1, -1); add(bit[t][b % m], b / m + 1, 1); ts[b] = t; } else { if((int)vec.size() != m) continue; rep(j, 0, m) { int l, r; l = (a - j + m - 1) / m; r = (b - j + m) / m; int t = vec[(j - a % m + m) % m]; ans[i] += sum(bit[t][j], r) - sum(bit[t][j], l); } } } } rep(i, 0, Q) { if(ans[i] == -1) continue; cout << ans[i] << "\n"; } }
添え字は数学で考えればミスらないで済むね。