結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; }