結果

問題 No.876 Range Compress Query
ユーザー lowrlowr
提出日時 2019-09-07 16:50:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 298 ms / 2,000 ms
コード長 3,533 bytes
コンパイル時間 2,138 ms
コンパイル使用メモリ 211,104 KB
実行使用メモリ 13,808 KB
最終ジャッジ日時 2023-09-09 04:49:19
合計ジャッジ時間 5,590 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 3 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 3 ms
4,380 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 296 ms
13,136 KB
testcase_12 AC 243 ms
12,884 KB
testcase_13 AC 248 ms
13,268 KB
testcase_14 AC 292 ms
13,276 KB
testcase_15 AC 201 ms
13,480 KB
testcase_16 AC 284 ms
13,616 KB
testcase_17 AC 289 ms
13,808 KB
testcase_18 AC 298 ms
13,744 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using i64 = long long;

template <typename T, typename U = T>
class LazySegmentTree {
    int size;
    T tid;
    T *dat;
    U uid;
    U *lazy;

    inline T f(T a, T b) {
        auto [na, la, ra] = a;
        auto [nb, lb, rb] = b;
        int n = na + nb + (ra >= 0 && ra == lb);
        return std::make_tuple(n, la, rb);
    }

    inline T g(T t, U u, int len) {
        auto [n, l, r] = t;
        return std::make_tuple(n, l + u, r + u);
    }

    inline U h(U a, U b) {
        return a + b;
    }

    void propagate(int k, int l, int r) {
        if (lazy[k] == uid) return;

        if (k < size - 1) {
            lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
            lazy[2 * k + 2] = h(lazy[2 * k + 2], lazy[k]);
        }

        dat[k] = g(dat[k], lazy[k], r - l);
        lazy[k] = uid;
    }

    T update_impl(int a, int b, U x, int k, int l, int r) {
        propagate(k, l, r);
        if (r <= a || b <= l) return dat[k];
        if (a <= l && r <= b) {
            lazy[k] = h(lazy[k], x);
            propagate(k, l, r);
            return dat[k];
        }

        return dat[k] = f(update_impl(a, b, x, 2 * k + 1, l, (l + r) / 2),
                          update_impl(a, b, x, 2 * k + 2, (l + r) / 2, r));
    }

    T query_impl(int a, int b, int k, int l, int r) {
        propagate(k, l, r);
        if (r <= a || b <= l) return tid;
        if (a <= l && r <= b) return dat[k];
        return f(query_impl(a, b, 2 * k + 1, l, (l + r) / 2),
                 query_impl(a, b, 2 * k + 2, (l + r) / 2, r));
    }

public:
    LazySegmentTree(const int n, const T &tid, const U &uid) : tid(tid), uid(uid) {
        size = 2;
        while (size < n) size *= 2;
        dat = new T[2 * size - 1];
        lazy = new U[2 * size - 1];

        for (int i = 0; i < 2 * size - 1; i++) {
            dat[i] = tid;
            lazy[i] = uid;
        }
    }

    template <template <class> class Container>
    LazySegmentTree(const Container<T> &v, const T &tid, const U &uid) : tid(tid), uid(uid) {
        int n = v.size();
        size = 2;
        while (size < n) size *= 2;
        dat = new T[2 * size - 1];
        lazy = new U[2 * size - 1];

        for (int i = 0; i < n; i++) dat[i + size - 1] = v[i];
        for (int i = size - 1 + n; i < 2 * size - 1; i++) dat[i] = tid;
        for (int i = 0; i < 2 * size - 1; i++) lazy[i] = uid;
        dig(0);
    }

    void dig(int v) {
        if (v >= size - 1) return;
        dig(2 * v + 1);
        dig(2 * v + 2);
        dat[v] = f(dat[2 * v + 1], dat[2 * v + 2]);
    }

    ~LazySegmentTree() {
        delete[] dat;
        delete[] lazy;
    }

    void update(const int a, const int b, const U x) {
        update_impl(a, b, x, 0, 0, size);
    }

    T query(const int a, const int b) {
        return query_impl(a, b, 0, 0, size);
    }

    T operator[](const int i) {
        return query(i, i + 1);
    }
};

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<std::tuple<int, i64, i64>> v;
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        v.emplace_back(0, a, a);
    }

    auto lst = LazySegmentTree(v, std::make_tuple(0, -1ll, -1ll), 0ll);

    while (q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        l--;
        if (t == 1) {
            i64 x;
            std::cin >> x;
            lst.update(l, r, x);
        } else {
            std::cout << r - l - std::get<0>(lst.query(l, r)) << std::endl;
        }
    }

    return 0;
}
0