結果

問題 No.3265 地元に帰れば天才扱い！
コンテスト
ユーザー 3atnk
提出日時 2025-09-06 21:51:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,057 ms / 2,500 ms
コード長 4,939 bytes
コンパイル時間 1,723 ms
コンパイル使用メモリ 126,824 KB
実行使用メモリ 28,288 KB
最終ジャッジ日時 2025-09-06 21:52:01
合計ジャッジ時間 31,784 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <atcoder/lazysegtree>

// AtCoder Libraryと標準ライブラリの名前空間を使用
using namespace std;
using namespace atcoder;

// --- 1つ目の遅延セグメント木 (seg) のための定義 ---
// 区間加算・区間最小値取得 (RAQ/RMQ)

// S: モノイドの型 (ここでは最小値)
using S1 = long long;
// F: 作用素の型 (ここでは加算する値)
using F1 = long long;

// 二項演算 op(a, b): aとbの最小値を返す
S1 op1(S1 a, S1 b) { return min(a, b); }
// 単位元 e: minの単位元は無限大
S1 e1() { return 1e18; } // PythonのINFに対応
// 作用 mapping(f, x): 作用素fをモノイドxに適用 (加算)
S1 mapping1(F1 f, S1 x) { return f + x; }
// 作用の合成 composition(f, g): 新しい作用fと古い作用gを合成 (加算)
F1 composition1(F1 f, F1 g) { return f + g; }
// 作用の単位元 id: 加算の単位元は0
F1 id1() { return 0; }


// --- 2つ目の遅延セグメント木 (seg2) のための定義 ---
// 区間加算・区間和取得 (RAQ/RSQ)

// S: モノイドの型 {値の和, 区間の長さ} のペア
struct S2 {
    long long value;
    long long size;
};
// F: 作用素の型 (加算する値)
using F2 = long long;

// 二項演算 op(a, b): 2つのペアをマージ
S2 op2(S2 a, S2 b) { return {a.value + b.value, a.size + b.size}; }
// 単位元 e: 和の単位元は0, 長さの単位元も0
S2 e2() { return {0, 0}; }
// 作用 mapping(f, x): 作用素fをモノイドxに適用
// 値の和は (f * 区間長) だけ増える
S2 mapping2(F2 f, S2 x) { return {x.value + f * x.size, x.size}; }
// 作用の合成 composition(f, g): 加算なので和
F2 composition2(F2 f, F2 g) { return f + g; }
// 作用の単位元 id: 加算の単位元は0
F2 id2() { return 0; }

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    vector<long long> lst(N);
    vector<int> place(N);
    vector<pair<int, int>> jimoto(N);

    // Pythonの初期化に対応
    vector<S1> house(M, 0);
    vector<S2> house2(M);
    for(int i = 0; i < M; ++i) {
        house2[i] = {0, 1};
    }

    for (int i = 0; i < N; ++i) {
        long long a;
        int b, c;
        cin >> a >> b >> c;
        lst[i] = a;
        jimoto[i] = {b - 1, c - 1};
        place[i] = i; // 初期位置はi
    }
    
    // 遅延セグメント木のインスタンス化
    lazy_segtree<S1, op1, e1, F1, mapping1, composition1, id1> seg(house);
    lazy_segtree<S2, op2, e2, F2, mapping2, composition2, id2> seg2(house2);

    // Pythonの lst[i] を house2 に反映する部分に対応
    // 初期状態では place[i] == i なので、seg2のi番目にlst[i]をセット
    for (int i = 0; i < N; ++i) {
        seg2.set(i, {lst[i], 1});
    }

    // 初期状態の計算
    for (int i = 0; i < N; ++i) {
        seg.apply(jimoto[i].first, jimoto[i].second + 1, 1);
    }

    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += lst[i] * (jimoto[i].second - jimoto[i].first + 1);
        // 初期状態では place[i] == i
        ans -= seg.get(i) * lst[i];
    }
    
    int Q;
    cin >> Q;
    while (Q--) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        // 0-indexedに変換
        x--; y--; u--; v--;

        long long val = lst[x];
        int old_place = place[x];
        pair<int, int> old_jimoto = jimoto[x];

        // 1. 古い状態の寄与をansから引く
        ans -= val * (old_jimoto.second - old_jimoto.first + 1);
        ans += seg.get(old_place) * val;
        
        S2 prod_res_old = seg2.prod(old_jimoto.first, old_jimoto.second + 1);
        ans += prod_res_old.value;

        if (old_jimoto.first <= old_place && old_place <= old_jimoto.second) {
            ans -= val;
        }

        // 2. セグメント木の状態を更新
        // seg2: 古い場所から値を削除
        seg2.apply(old_place, old_place + 1, -val);
        // seg: 古い地元範囲の重複カウントをデクリメント
        seg.apply(old_jimoto.first, old_jimoto.second + 1, -1);
        
        // seg2: 新しい場所に値を追加
        seg2.apply(y, y + 1, val);
        // seg: 新しい地元範囲の重複カウントをインクリメント
        seg.apply(u, v + 1, 1);
        
        // 3. データの状態を更新
        place[x] = y;
        jimoto[x] = {u, v};
        
        // 4. 新しい状態の寄与をansに足す
        ans += val * (jimoto[x].second - jimoto[x].first + 1);
        ans -= seg.get(place[x]) * val;

        S2 prod_res_new = seg2.prod(jimoto[x].first, jimoto[x].second + 1);
        ans -= prod_res_new.value;
        
        if (jimoto[x].first <= place[x] && place[x] <= jimoto[x].second) {
            ans += val;
        }
        
        cout << ans << "\n";
    }

    return 0;
}
0