はまやんはまやんはまやん

hamayanhamayan's blog

Range Compress Query [yukicoder 876]

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