「みんなのプロコン」本選C: 倍数クエリ

https://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_c

平方分割やるだけです。

初期化の時にセグフォ起こしたのでそれだけ気をつけましょう。

const int BLOCK = 300;
const int CNT = MAX_N / BLOCK + 10;

int N, M;
int Q;

ll A[MAX_N];
int B[CNT];
int C[CNT][BLOCK];
int D[CNT][MAX_N];

void push(int id) {
	for(int i = id * BLOCK; i < (id + 1) * BLOCK; i++) {
		A[i] += B[id];
		A[i] %= M;
	}
	B[id] = 0;
}

void pull(int id, bool first = false) {
	rep(i, 0, BLOCK) {
		if(!first) D[id][C[id][i]]--;
		C[id][i] = A[id * BLOCK + i];
		D[id][C[id][i]]++;
	}
}

void update_block(int id, int k) {
	B[id] += k;
	B[id] %= M;
}

int get_block(int id) {
	return D[id][(M - B[id]) % M];
}

void solve() {
	cin >> N >> M >> Q;
	rep(i, 0, N) {
		cin >> A[i];
		A[i] %= M;
	}
	rep(id, 0, N / BLOCK + 1) pull(id, true);

	while(Q--) {
		int l, r, k;
		cin >> l >> r >> k; l--;
		k %= M;

		int cnt = 0;

		int lid = l / BLOCK, rid = r / BLOCK;
		push(lid); push(rid);
		while(l < r && l < (lid + 1) * BLOCK) {
			A[l] += k;
			A[l] %= M;
			if(!A[l]) cnt++;
			l++;
		}
		while(l < r && r > rid * BLOCK) {
			A[r - 1] += k;
			A[r - 1] %= M;
			if(!A[r - 1]) cnt++;
			r--;
		}
		pull(lid); pull(rid);
		for(int id = lid + 1; id < rid; id++) {
			update_block(id, k);
			cnt += get_block(id);
		}
		cout << cnt << "\n";
	}
}