結果

問題 No.876 Range Compress Query
ユーザー Y17Y17
提出日時 2019-09-06 21:57:57
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 430 ms / 2,000 ms
コード長 3,514 bytes
コンパイル時間 1,635 ms
コンパイル使用メモリ 169,556 KB
実行使用メモリ 11,504 KB
最終ジャッジ日時 2024-06-24 17:48:25
合計ジャッジ時間 5,701 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 4 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 4 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 422 ms
11,392 KB
testcase_12 AC 346 ms
11,504 KB
testcase_13 AC 346 ms
11,228 KB
testcase_14 AC 420 ms
11,392 KB
testcase_15 AC 288 ms
11,392 KB
testcase_16 AC 407 ms
11,376 KB
testcase_17 AC 410 ms
11,392 KB
testcase_18 AC 430 ms
11,264 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define int long long

template< typename Monoid, typename OperatorMonoid = Monoid >
struct LazySegmentTree {
    using F = function< Monoid(Monoid, Monoid) >;
    using G = function< Monoid(Monoid, OperatorMonoid, int) >;
    using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;

    int sz;
    vector< Monoid > data;
    vector< OperatorMonoid > lazy;
    const F f;
    const G g;
    const H h;
    const Monoid M1;
    const OperatorMonoid OM0;


    LazySegmentTree(int n, const F f, const G g, const H h,
            const Monoid &M1, const OperatorMonoid OM0)
        : f(f), g(g), h(h), M1(M1), OM0(OM0) {
            sz = 1;
            while(sz < n) sz <<= 1;
            data.assign(2 * sz, M1);
            lazy.assign(2 * sz, OM0);
        }

    void set(int k, const Monoid &x) {
        data[k + sz] = x;
    }

    void build() {
        for(int k = sz - 1; k > 0; k--) {
            data[k] = f(data[2 * k + 0], data[2 * k + 1]);
        }
    }

    void propagate(int k, int len) {
        if(lazy[k] != OM0) {
            if(k < sz) {
                lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
                lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
            }
            data[k] = g(data[k], lazy[k], len);
            lazy[k] = OM0;
        }
    }

    Monoid update(int a, int b, const OperatorMonoid &x, int k, int l, int r) {
        propagate(k, r - l);
        if(r <= a || b <= l) {
            return data[k];
        } else if(a <= l && r <= b) {
            lazy[k] = h(lazy[k], x);
            propagate(k, r - l);
            return data[k];
        } else {
            return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),
                    update(a, b, x, 2 * k + 1, (l + r) >> 1, r));
        }
    }

    Monoid update(int a, int b, const OperatorMonoid &x) {
        return update(a, b, x, 1, 0, sz);
    }


    Monoid query(int a, int b, int k, int l, int r) {
        propagate(k, r - l);
        if(r <= a || b <= l) {
            return M1;
        } else if(a <= l && r <= b) {
            return data[k];
        } else {
            return f(query(a, b, 2 * k + 0, l, (l + r) >> 1),
                    query(a, b, 2 * k + 1, (l + r) >> 1, r));
        }
    }

    Monoid query(int a, int b) {
        return query(a, b, 1, 0, sz);
    }

    Monoid operator[](const int &k) {
        return query(k, k + 1);
    }
};

struct Data{
    int cnt;
    int l;
    int r;
};

Data make(int a){
    Data d;
    d.cnt = 0;
    d.l = a;
    d.r = a;
    return d;
}

Data mer(Data a, Data b){
    Data ans;
    if(a.l == -1) return b;
    if(b.l == -1) return a;
    ans.cnt = a.cnt + b.cnt;
    if(a.r != b.l){
        ans.cnt++;
    }
    ans.l = a.l;
    ans.r = b.r;
    return ans;
}

Data merge2(Data a, int b, int x){
    a.l += b;
    a.r += b;
    return a;
}

int merge3(int a, int b){
    return a+b;
}

signed main(){
    int n, q;
    cin >> n >> q;

    LazySegmentTree<Data, int> seg(n, mer, merge2, merge3, make(-1), 0);

    for(int i = 0;i < n;i++){
        int a;
        cin >> a;
        seg.set(i, make(a));
    }

    seg.build();

    for(int p = 0;p < q;p++){
        int a;
        cin >> a;
        if(a == 1){
            int l, r, x;
            cin >> l >> r >> x;
            seg.update(l-1, r, x);
        }else{
            int l, r;
            cin >> l >> r;
            cout << seg.query(l-1, r).cnt+1 << endl;
        }
    }

    return 0;
}
0