#1156642 (C++17) No.3494 一点挿入区間和取得

• 問題: No.3494 一点挿入区間和取得
• ユーザー: The Forsaking
• 提出日時: 2026-04-04 16:29:00
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 57 ms / 6,000 ms
• コード長: 3,116 bytes
• コンパイル時間: 1,657 ms
• コンパイル使用メモリ: 216,088 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-04 16:29:41
• 合計ジャッジ時間: 2,547 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

ファイルパターン	結果
other	AC * 23

ソースコード

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000010, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];


struct Splay {
    struct node {
        int s[2], v, p;
        int size;
        ll sum;
        void init(int _v, int _p) {
            s[0] = s[1] = 0;
            sum = v = _v, p = _p, size = 1;
        }
    };

    vector<node> tr;
    int root, idx;

    Splay(int n = 0) {
	    init(n);
    }

    void init(int n) {
        tr.assign(n + 1, {});
        root = idx = 0;
    }

    void pushup(int u) {
        tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
        tr[u].sum = tr[tr[u].s[0]].sum + tr[tr[u].s[1]].sum + tr[u].v;
    }

    void rotate(int x) {
        int y = tr[x].p, z = tr[y].p;
        int k = (tr[y].s[1] == x);
        tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
        tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[y].s[k]].p = y;
        tr[x].s[k ^ 1] = y, tr[y].p = x;
        pushup(y), pushup(x);
    }

    void splay(int x, int k = 0) {
        while (tr[x].p != k) {
            int y = tr[x].p, z = tr[y].p;
            if (z != k) {
                if ((tr[y].s[0] == x) ^ (tr[z].s[0] == y)) rotate(x);
                else rotate(y);
            }
            rotate(x);
        }
        if (!k) root = x;
    }

    int newnode(int v, int p) {
        if (++idx >= tr.size()) tr.push_back({});
        tr[idx].init(v, p);
        return idx;
    }

    void insert(int v, int r) {
        int u = 0, p = r ? get_k(r) : 0;
        if (p && tr[p].s[1]) splay(get_k(r + 1));
        u = newnode(v, p);
        if (p) tr[p].s[1] = u;
        splay(u, 0);
    }

    int get_k(int k) {
        int u = root;
        while (u) {
            if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
            else if (tr[tr[u].s[0]].size + 1 == k) {
                splay(u);
                return u;
            } else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
        }
        return -1;
    }

    int get_v(int v) {
        int u = root;
        while (u) {
            if (tr[u].v == v) {
                splay(u, 0);
                return u;
            }
            u = tr[u].s[v > tr[u].v];
        }
        return -1;
    }

    void erase(int v) {
        int u = get_v(v);
        splay(u, 0);
        int l = tr[u].s[0], r = tr[u].s[1];
        while (tr[l].s[1]) l = tr[l].s[1];
        while (tr[r].s[0]) r = tr[r].s[0];
        splay(l, 0), splay(r, l);
        tr[r].s[0] = 0;
        pushup(r), pushup(l);
    }
};

void solve() {
    scanf("%d%d", &n, &m);
    Splay tr(n + m + 2);
    tr.insert(-INF, 0);
    for (int i = 1, a; i < n + 1; i++) {
        scanf("%d", &a);
        tr.insert(a, i);
    }
    tr.insert(INF, n + 1);
    while (m--) {
        int i, x, l, r;
        scanf("%d%d%d%d", &i, &x, &l, &r);
        tr.insert(x, i + 1);
        int pl = tr.get_k(l), pr = tr.get_k(r + 2);
        tr.splay(pl), tr.splay(pr, pl);
        printf("%lld\n", tr.tr[tr.tr[pr].s[0]].sum);
    }
}

int main() {
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}