結果

問題 No.876 Range Compress Query
コンテスト
ユーザー zelda_master
提出日時 2026-07-27 13:28:42
言語 C++14
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 38 ms / 2,000 ms
+ 973µs
コード長 1,096 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 308 ms
コンパイル使用メモリ 73,984 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-07-27 13:28:44
合計ジャッジ時間 2,702 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 100010;

LL cf[N];
int n, q, a[N];

struct BIT {
    LL tr[N];
    int LowBit(int x) { return x & -x; }
    void Add(int x, int v) {
        for (int i = x; i <= n; i += LowBit(i)) tr[i] += v;
    }
    LL Sum(int x) {
        LL ret = 0LL;
        for (int i = x; i; i -= LowBit(i)) ret += tr[i];
        return ret;
    }
};
BIT bit;

void Modify(int x, LL v) {
    if (cf[x] != 0) bit.Add(x, -1);
    cf[x] += v;
    if (cf[x] != 0) bit.Add(x, 1);
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 2; i <= n; ++i) {
        cf[i] = a[i] - a[i - 1];
        if (cf[i] != 0) bit.Add(i, 1);
    }
    while (q--) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1) {
            LL x;
            scanf("%lld", &x);
            if (l > 1) Modify(l, x);
            if (r < n) Modify(r + 1, -x);
        } else {
            printf("%lld\n", bit.Sum(r) - bit.Sum(l) + 1);
        }
    }

    return 0;
}
0