結果

問題 No.3265 地元に帰れば天才扱い！
コンテスト
ユーザー hamikan
提出日時 2025-09-06 18:27:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,436 ms / 2,500 ms
コード長 5,716 bytes
コンパイル時間 2,356 ms
コンパイル使用メモリ 204,636 KB
実行使用メモリ 29,976 KB
最終ジャッジ日時 2025-09-06 18:28:12
合計ジャッジ時間 35,704 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

struct Ops1 {
    struct T {
        ll val;
        int size;
    };

    using F = ll;
    
    static constexpr T identity = {0, 1};
    static constexpr F lazy_identity = 0;
    static T op(T a, T b) {return {a.val + b.val, a.size + b.size};}
    static T mapping(F f, T x) {return {x.val + f * x.size, x.size};}
    static F composition(F f, F g) {return f + g;}
    static bool ok(T a) {return true;}
};

template<typename Ops>
struct LazySegTree {
    using T = typename Ops::T;
    using F = typename Ops::F;

    int N, size, log;
    vector<T> tree1;
    vector<F> lazy;

    LazySegTree(int N) : LazySegTree(vector<T>(N, Ops::identity)) {}
    LazySegTree(const vector<T>& arr) : N(arr.size()), size(1), log(0) {
        while(size < N) size <<= 1, log++;
        tree1.assign(2 * size, Ops::identity);
        lazy.assign(size, Ops::lazy_identity);
        for(int i=0; i<N; i++) tree1[size+i] = arr[i];
        for(int i=size-1; i>0; i--) update(i);
    }

    void set(int p, T x) {
        p += size;
        for(int i=log; i>=1; i--) push(p >> i);
        tree1[p] = x;
        for(int i=1; i<=log; i++) update(p >> i);
    }

    T operator[](int p) {
        p += size;
        for(int i=log; i>=1; i--) push(p >> i);
        return tree1[p];
    }

    T query(int l, int r) {
        if(l == r) return Ops::identity;
        T ret = Ops::identity;
        l += size, r += size;
        for(int i=log; i>=1; i--) {
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push((r - 1) >> i);
        }
        while(l < r) {
            if(l & 1) ret = Ops::op(ret, tree1[l++]);
            if(r & 1) ret = Ops::op(ret, tree1[--r]);
            l >>= 1, r >>= 1;
        }
        return ret;
    }

    T all_query() {
        return tree1[1];
    }

    void apply(int p, F f) {
        p += size;
        for(int i=log; i>=1; i--) push(p >> i);
        tree1[p] = Ops::mapping(f, tree1[p]);
        for(int i=1; i<=log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        if(l == r) return;
        l += size, r += size;
        for(int i=log; i>=1; i--) {
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push((r - 1) >> i);
        }
        int tl = l, tr = r;
        while(l < r) {
            if(l & 1) all_apply(l++, f);
            if(r & 1) all_apply(--r, f);
            l >>= 1, r >>= 1;
        }
        l = tl, r = tr;
        for(int i=1; i<=log; i++) {
            if(((l >> i) << i) != l) update(l >> i);
            if(((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    int max_right(int l) {
        if(l == N) return N;
        l += size;
        for(int i=log; i>=1; i--) push(l >> i);
        T acc = Ops::identity;
        do {
            while((l & 1) == 0) l >>= 1;
            if(!Ops::ok(Ops::op(acc, tree1[l]))) {
                while(l < size) {
                    push(l);
                    l <<= 1;
                    if(Ops::ok(Ops::op(acc, tree1[l]))) {
                        acc = Ops::op(acc, tree1[l]);
                        l++;
                    }
                }
                return l - size;
            }
            acc = Ops::op(acc, tree1[l]);
            l++;
        } while((l & -l) != l);
        return N;
    }

    int min_left(int r) {
        if(r == 0) return 0;
        r += size;
        for(int i=log; i>=1; i--) push((r - 1) >> i);
        T acc = Ops::identity;
        do {
            r--;
            while(r > 1 && (r & 1)) r >>= 1;
            if(!Ops::ok(Ops::op(acc, tree1[r]))) {
                while(r < size) {
                    push(r);
                    r = (r << 1) + 1;
                    if(Ops::ok(Ops::op(acc, tree1[r]))) {
                        acc = Ops::op(acc, tree1[r]);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            acc = Ops::op(acc, tree1[r]);
        } while((r & -r) != r);
        return 0;
    }

    void update(int p) {tree1[p] = Ops::op(tree1[p*2], tree1[p*2+1]);}

    void all_apply(int k, F f) {
        tree1[k] = Ops::mapping(f, tree1[k]);
        if(k < size) lazy[k] = Ops::composition(f, lazy[k]);
    }
    
    void push(int k) {
        all_apply(2 * k, lazy[k]);
        all_apply(2 * k + 1, lazy[k]);
        lazy[k] = Ops::lazy_identity;
    }

    void debug() {
        for(int i=1; i<=2*size; i++) cout << tree1[i-1].val << " \n"[(i & -i) == i];
        for(int i=2; i<=size; i++) cout << lazy[i-1] << " \n"[(i & -i) == i];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N, M, ans = 0;
    cin >> N >> M;
    LazySegTree<Ops1> tree1(M), tree2(M);
    vector<ll> A(N), L(N), R(N), H(N);
    for(int i=0; i<N; i++) {
        cin >> A[i] >> L[i] >> R[i];
        tree1.apply(L[i] - 1, R[i], 1LL);
        ans += (R[i] - (L[i] - 1)) * A[i];
        H[i] = i;
        tree2.set(i, Ops1::T{A[i], 1});
    }
    for(int i=0; i<N; i++) ans -= A[i] * tree1[i].val;
    int Q;
    cin >> Q;
    while(Q--) {
        int X, Y, U, V;
        cin >> X >> Y >> U >> V;
        X--, Y--;
        ans += tree1[H[X]].val * A[X];
        ans -= (R[X] - (L[X] - 1)) * A[X];
        tree2.set(H[X], Ops1::T{0, 0});
        ans += tree2.query(L[X] - 1, R[X]).val;
        tree1.apply(L[X] - 1, R[X], -1);
        tree1.apply(U - 1, V, 1); 
        ans -= tree1[Y].val * A[X];
        ans += (V - (U - 1)) * A[X];
        ans -= tree2.query(U - 1, V).val;
        tree2.set(Y, Ops1::T{A[X], 1});
        cout << ans << endl;
        H[X] = Y;
        L[X] = U;
        R[X] = V;
    }
}
0