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