結果

問題 No.876 Range Compress Query
ユーザー taklimonetaklimone
提出日時 2019-11-21 18:14:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 390 ms / 2,000 ms
コード長 3,711 bytes
コンパイル時間 2,407 ms
コンパイル使用メモリ 208,380 KB
実行使用メモリ 13,824 KB
最終ジャッジ日時 2024-04-19 03:09:00
合計ジャッジ時間 6,735 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 376 ms
13,184 KB
testcase_12 AC 311 ms
12,928 KB
testcase_13 AC 322 ms
13,184 KB
testcase_14 AC 380 ms
13,184 KB
testcase_15 AC 258 ms
13,440 KB
testcase_16 AC 364 ms
13,696 KB
testcase_17 AC 363 ms
13,824 KB
testcase_18 AC 390 ms
13,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template <typename T, typename E>
class lazy_segtree {
private:
    using Op = function<T(T, T)>;
    using Compose = function<E(E, E)>;
    using Act = function<T(T, E)>;
    using Power = function<E(E, int)>;

    size_t N;
    vector<T> data;
    vector<E> lazy;
    const T idT;
    const E idE;
    const Op op;
    const Compose compose;
    const Act act;
    const Power power;

    void eval(size_t k, size_t len) {
        if(lazy[k] == idE) return;
        if(2 * k + 1 < 2 * N) {
            lazy[2 * k] = compose(lazy[2 * k], lazy[k]);
            lazy[2 * k + 1] = compose(lazy[2 * k + 1], lazy[k]);
        }
        data[k] = act(data[k], power(lazy[k], len));
        lazy[k] = idE;
    }

    void update(size_t a, size_t b, size_t k, size_t l, size_t r, E x) {
        eval(k, r - l);
        if(r <= a || b <= l) return;
        if(a <= l && r <= b) {
            lazy[k] = compose(lazy[k], x);
            eval(k, r - l);
            return;
        }
        update(a, b, 2 * k, l, (l + r) / 2, x);
        update(a, b, 2 * k + 1, (l + r) / 2, r, x);
        data[k] = op(data[2 * k], data[2 * k + 1]);
    }

    T get(size_t a, size_t b, size_t k, size_t l, size_t r) {
        eval(k, r - l);

        if(r <= a || b <= l) return idT;
        if(a <= l && r <= b) return data[k];
        
        T vl = get(a, b, 2 * k, l, (l + r) / 2);
        T vr = get(a, b, 2 * k + 1, (l + r) / 2, r);
        if(2 * k + 1 < 2 * N) data[k] = op(data[2 * k], data[2 * k + 1]);
        return op(vl, vr);
    }

public:
    lazy_segtree(size_t n, T idT, E idE,
    const Op op, const Compose compose,
    const Act act, const Power power = [](E a, int){ return a; })
    : idT(idT), idE(idE), op(op), compose(compose), act(act), power(power) {
        for(N = 1; N < n; N <<= 1);
        data = vector<T>(2 * N, idT);
        lazy = vector<E>(2 * N, idE);
    }
    
    lazy_segtree(const vector<T> &init, T idT, E idE,
    const Op op, const Compose compose,
    const Act act, const Power power = [](E a, int){ return a; })
    : idT(idT), idE(idE), op(op), compose(compose), act(act), power(power) {
        for(N = 1; N < init.size(); N <<= 1);
        data = vector<T>(2 * N, idT);
        lazy = vector<E>(2 * N, idE);
        for(size_t i = 0; i < init.size(); ++i) data[i + N] = init[i];
        for(size_t i = N - 1, last = -1; i != last; --i) data[i] = op(data[2 * i], data[2 * i + 1]);
    }

    void update(size_t left, size_t right, E x) {
        update(left, right, 1, 0, N, x);
    }

    T get(size_t left, size_t right) {
        return get(left, right, 1, 0, N);
    }

    T operator[](int k) {
        return get(k, k + 1);
    }
};

struct node {
    long long left;
    long long right;
    int cnt;
    node(): left(0), right(0), cnt(0) {};
    node(long long left, long long right, int cnt = 1)
    :left(left), right(right), cnt(cnt){}
};

int main() {
    int N, Q; cin >> N >> Q;
    vector<node> A(N);
    for(int i=0; i<N; ++i) {
        long long a; cin >> a;
        A[i] = node(a, a, 1);
    }
    
    auto op = [](node const& a, node const& b) {
        if(a.cnt == 0) return b;
        else if(b.cnt == 0) return a;
        else return node(a.left, b.right, a.cnt + b.cnt - (a.right == b.left ? 1 : 0));
    };
    lazy_segtree<node, long long> tree(A, node(0, 0, 0), 0,
    op, plus<long long>(),
    [](const node& a, long long x){ return node(a.left + x, a.right + x, a.cnt); });

    while(Q--) {
        int k,l,r; cin >> k >> l >> r;
        if(k == 1) {
            int x; cin >> x;
            tree.update(l - 1, r, x);
        } else {
            cout << tree.get(l - 1, r).cnt << endl;
        }
    }
}
0