https://yukicoder.me/problems/no/876
解説
https://yukicoder.me/submissions/377914
問題をよく見ると、隣り合う数が異なる組+1を答える問題になっている。
つまり、数の実際の大小は特に意味がない。
加えて、今回は区間addのクエリもあるため、階差を使う問題だと推測できる。
b[i]=a[i + 1]-a[i]として階差を取る。
すると、クエリ1の区間更新[L,R]はB[L-1]+=x, B[R]-=xと2点を更新するだけでよくなる。
クエリ2の差が0かそうでないかという部分は、階差そのもの。
あとは、クエリ2の高速化であるが、クエリ1の更新は2箇所だけであるため、
更新されたら更新するようにすれば、BITを使った高速化が見込める。
階差bを0ならば0, 0でないなら1として、BITに乗せておこう。
これでクエリ2はBIT[L,R-1]+1が答えになる。
int N, Q; ll A[101010]; ll B[101010]; BIT<int> bit(101010); //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> Q; rep(i, 0, N) cin >> A[i]; rep(i, 0, N - 1) { B[i] = A[i + 1] - A[i]; if(B[i] != 0) bit.update(i, 1); } rep(i, 0, Q) { int t; cin >> t; if(t == 1) { int l, r, x; cin >> l >> r >> x; l--; r--; if(l) { bit.update(l - 1, 0); B[l - 1] += x; if(B[l - 1] != 0) bit.update(l - 1, 1); } bit.update(r, 0); B[r] -= x; if(B[r] != 0) bit.update(r, 1); } else { int l, r; cin >> l >> r; l--; r--; int ans = bit.get(l, r) + 1; printf("%d\n", ans); } } }