Codeforces Round #423C: DNA Evolution

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";
	}
}

添え字は数学で考えればミスらないで済むね。