結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー Jikky1618
提出日時 2025-09-06 15:56:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 336 ms / 2,500 ms
コード長 4,348 bytes
コンパイル時間 3,403 ms
コンパイル使用メモリ 285,072 KB
実行使用メモリ 12,800 KB
最終ジャッジ日時 2025-09-06 15:56:23
合計ジャッジ時間 14,296 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...)
#endif

template <class T>
struct BinaryIndexedTree {
    int N;
    vector<T> data;

    BinaryIndexedTree() = default;
    BinaryIndexedTree(int size) : N(size), data(size + 1, 0) {}
    BinaryIndexedTree(const vector<T>& v) : N(ssize(v)), data(N + 1) {
        for (int i = 1; i <= N; i++) {
            data[i] += v[i - 1];
            int j = i + (i & -i);
            if (j <= N) data[j] += data[i];
        }
    }

    // i 番目に x を加算
    void add(int i, T x) {
        assert(0 <= i && i < N);
        for (++i; i <= N; i += i & -i) data[i] += x;
    }
    // i 番目を x に更新
    void set(int i, T x) {
        assert(0 <= i && i < N);
        T diff = x - sum(i, i + 1);
        for (++i; i <= N; i += i & -i) data[i] += diff;
    }
    // [l, r) に x を加算 (imos 法)
    void imos(int l, int r, T x) { add(l, x), add(r, -x); }
    // [0, i) の和 (imos 法で区間加算して i 番目の値を取るときは sum(i + 1))
    T sum(int i) const {
        if (i < 0) return T{};
        T res{};
        for (; i > 0; i -= i & -i) res += data[i];
        return res;
    }
    // [l, r) の和
    T sum(int l, int r) const { return sum(r) - sum(l); }
    // i 番目の値
    T operator[](int i) const { return sum(i + 1) - sum(i); }
    // [0, i) の和が w 以上となる最小の i
    int lower_bound(T w) const {
        if (w <= 0) return 0;
        int i = 0;
        for (int k = 1 << __lg(N); k > 0; k >>= 1) {
            if (i + k <= N && data[i + k] < w) {
                w -= data[i + k];
                i += k;
            }
        }
        return i + 1;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N, M;
    cin >> N >> M;
    vector<ll> A(M), L(N), R(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> L[i] >> R[i], L[i]--;
    int Q;
    cin >> Q;

    // H[i] := 家 i に住んでいる岩井星人の id
    vector<int> H(M, -1);
    iota(H.begin(), H.begin() + N, 0);
    // I[i] := 岩井星人 i が住んでいる家の id
    vector<int> I(N);
    iota(I.begin(), I.end(), 0);

    // 初期状態の天才度の総和を求める
    ll ans = 0;
    BinaryIndexedTree<ll> bit(A), bit2(M + 1);
    for (int i = 0; i < N; i++) {
        ans += (R[i] - L[i]) * A[I[i]] - (bit.sum(L[i], R[i]));
    }
    for (int i = 0; i < N; i++) {
        bit2.imos(L[i], R[i], 1);
    }
    while (Q--) {
        int X, Y, U, V;
        cin >> X >> Y >> U >> V, X--, Y--, U--;
        // 差分更新
        // 岩井星人 X の天才度を reset
        // for (int j = L[X]; j < R[X]; j++) {
        //     ans -= A[I[X]] - A[j];
        // }
        ans -= (R[X] - L[X]) * A[I[X]] - (bit.sum(L[X], R[X]));
        // 地元 [L[i], R[i]) に I[X] が含まれている岩井星人 i の岩井星人 X に関する天才度を reset
        // for (int i = 0; i < N; i++) {
        //     if (i == X) continue;
        //     if (L[i] <= I[X] && I[X] < R[i]) {
        //         // ans -= A[I[i]] - A[I[X]];
        //         // ans += A[I[i]];
        //         ans += A[I[X]];
        //     }
        // }
        ans += bit2.sum(I[X] + 1) * A[I[X]];
        ans -= (L[X] <= I[X] && I[X] < R[X]) ? A[I[X]] : 0;
        swap(H[I[X]], H[Y]);
        A[Y] = A[I[X]], A[I[X]] = 0;
        bit.set(Y, A[Y]), bit.set(I[X], 0);
        I[X] = Y;
        bit2.imos(L[X], R[X], -1), bit2.imos(U, V, 1);
        L[X] = U, R[X] = V;

        // 岩井星人 X の天才度を set
        // for (int j = L[X]; j < R[X]; j++) {
        //     ans += A[I[X]] - A[j];
        // }
        ans += (R[X] - L[X]) * A[I[X]] - (bit.sum(L[X], R[X]));
        // 地元 [L[i], R[i]) に I[X] が含まれている岩井星人 i の岩井星人 X に関する天才度を set
        // for (int i = 0; i < N; i++) {
        //     if (i == X) continue;
        //     if (L[i] <= I[X] && I[X] < R[i]) {
        //         // ans -= A[I[i]];
        //         // ans += A[I[i]] - A[I[X]];
        //         ans -= A[I[X]];
        //     }
        // }
        ans -= bit2.sum(I[X] + 1) * A[I[X]];
        ans += (L[X] <= I[X] && I[X] < R[X]) ? A[I[X]] : 0;

        cout << ans << "\n";
    }
}
0