結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー miya145592
提出日時 2025-09-06 15:57:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 871 ms / 2,500 ms
コード長 5,608 bytes
コンパイル時間 2,270 ms
コンパイル使用メモリ 208,140 KB
実行使用メモリ 25,132 KB
最終ジャッジ日時 2025-09-06 15:57:58
合計ジャッジ時間 24,870 ms
ジャッジサーバーID
（参考情報） 		judge / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long;

// ----- 普通のセグ木（総和）-----
struct SegTree {
    int _n, _size, _log;
    vector<long long> d; // 0 初期化

    SegTree(int n): _n(n) {
        _log = 0;
        while ((1 << _log) < _n) _log++;
        _size = 1 << _log;
        d.assign(_size << 1, 0LL);
    }

    // 位置pの値をxに設定
    void set_val(int p, long long x) {
        p += _size;
        d[p] = x;
        while (p >>= 1) {
            int l = p << 1, r = l | 1;
            d[p] = d[l] + d[r];
        }
    }

    // 位置pの値を取得
    long long get(int p) const { return d[p + _size]; }

    // 区間 [l, r) の総和
    long long prod(int l, int r) const {
        long long sml = 0, smr = 0;
        l += _size; r += _size;
        while (l < r) {
            if (l & 1) sml += d[l++];
            if (r & 1) smr += d[--r];
            l >>= 1; r >>= 1;
        }
        return sml + smr;
    }

    long long all_prod() const { return d[1]; }
};

// ----- 遅延セグ木：区間加算・区間和（点取得に使用）-----
struct LazySegTree {
    int n, log, size;
    vector<long long> d;   // 区間和
    vector<long long> lz;  // 遅延（加算）

    LazySegTree(int N) {
        n = N;
        log = 0;
        while ((1 << log) < n) log++;
        size = 1 << log;
        d.assign(2 * size, 0LL);
        lz.assign(size, 0LL);
    }

    // ノードkが表す区間長
    inline int seg_len(int k) const {
        int h = 31 - __builtin_clz(k);          // k のビット長-1
        int depth = log - h;                    // ルート深さlog
        return 1 << depth;
    }

    inline void apply_node(int k, long long f) {
        d[k] += f * seg_len(k);
        if (k < size) lz[k] += f;
    }

    inline void push(int k) {
        if (lz[k] != 0) {
            apply_node(k << 1, lz[k]);
            apply_node(k << 1 | 1, lz[k]);
            lz[k] = 0;
        }
    }

    inline void pull(int k) { d[k] = d[k << 1] + d[k << 1 | 1]; }

    // 区間 [l, r) に f を加算
    void apply(int l, int r, long long f) {
        if (l >= r) return;
        l += size; r += size;
        // push down
        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 l2 = l, r2 = r;
        while (l < r) {
            if (l & 1) apply_node(l++, f);
            if (r & 1) apply_node(--r, f);
            l >>= 1; r >>= 1;
        }
        l = l2; r = r2;
        for (int i = 1; i <= log; ++i) {
            if (((l >> i) << i) != l) pull(l >> i);
            if (((r >> i) << i) != r) pull((r - 1) >> i);
        }
    }

    // 位置 p の値（点取得）
    long long get(int p) {
        p += size;
        for (int i = log; i >= 1; --i) push(p >> i);
        return d[p];
    }

    // 区間和（今回は未使用）
    long long prod(int l, int r) {
        if (l >= r) return 0;
        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);
        }
        long long sml = 0, smr = 0;
        while (l < r) {
            if (l & 1) sml += d[l++];
            if (r & 1) smr += d[--r];
            l >>= 1; r >>= 1;
        }
        return sml + smr;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    if (!(cin >> N >> M)) return 0;
    struct Node { long long a; int l, r; };
    vector<Node> ALR(N);
    for (int i = 0; i < N; ++i) {
        long long a; int l, r;
        cin >> a >> l >> r;
        --l; --r;
        ALR[i] = {a, l, r};
    }
    int Q; cin >> Q;
    struct Query { int x, y, u, v; };
    vector<Query> qs(Q);
    for (int i = 0; i < Q; ++i) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        --x; --y; --u; --v;
        qs[i] = {x, y, u, v};
    }

    SegTree ST(M);
    LazySegTree ST2(M);
    vector<int> D; D.reserve(M);

    // 初期構築
    for (int i = 0; i < N; ++i) {
        auto [a, l, r] = ALR[i];
        ST.set_val(i, a);
        ST2.apply(l, r + 1, 1); // 区間カバレッジ+1
        D.push_back(i);
    }
    while ((int)ALR.size() < M) ALR.push_back({0, -1, -1});

    long long plus = 0, minus = 0;
    for (auto &t : ALR) {
        if (t.l == -1) continue;
        plus  += (long long)(t.r - t.l + 1) * t.a;
        minus += ST.prod(t.l, t.r + 1);
    }

    // クエリ処理
    for (auto &qq : qs) {
        int x = qq.x, y = qq.y, u = qq.u, v = qq.v;

        int xx = D[x];
        auto [a, l, r] = ALR[xx];

        // 旧区間の寄与を引く
        minus -= ST.prod(l, r + 1);
        {
            long long tmp = ST2.get(xx);
            if (l <= xx && xx <= r) minus -= (tmp - 1) * a;
            else                    minus -= (tmp) * a;
        }

        // 値の移動
        ST.set_val(xx, 0);
        ST.set_val(y, a);

        // カバレッジ更新
        ST2.apply(l, r + 1, -1);
        ST2.apply(u, v + 1, 1);

        // 新区間の寄与を足す
        minus += ST.prod(u, v + 1);
        {
            long long tmp = ST2.get(y);
            if (u <= y && y <= v) minus += (tmp - 1) * a;
            else                  minus += (tmp) * a;
        }

        // 情報更新
        ALR[y] = {a, u, v};
        D[x] = y;

        plus -= (long long)(r - l + 1) * a;
        plus += (long long)(v - u + 1) * a;

        long long ans = plus - minus;
        cout << ans << '\n';
    }
    return 0;
}
0