题解：AT_arc030_4 [ARC030D] グラフではない

· · 题解

可持久化平衡树好题！

题意简述：一个数组，三个操作。

第一眼这个题就有浓重的 DS 味，考虑使用哪个。

明显 BIT，线段树等不能满足题目要求。

看到区间复制，想到 FHQTreap。

因为它是我知道的唯一一个能把区间裂开来处理的结构。

对于这道题，一和三操作显然是模板题，具体来讲，类似线段树，对于每个节点维护这个节点掌管的区间内的和和懒标记。在向下递归和向上回溯的时候进行更新即可。

重点看二操作。

我们虽然说可以 O(\log n) 裂区间，但是复制区间仍然有些困难。

我们套用可持久化的思想，把用到的节点都复制一份，这样就可以直接把原本的区间夹到新的位置去了。

但是这里有个坑：由于每次操作都要复制，常数较大所以会 MLE。

对于这种情况，特判如果节点个数超过了阀值就中序遍历把数组存下来再重构整颗平衡树。

由于只是常数问题，所以重构的次数也是 O(1) 的。

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

#define int long long

constexpr int MAXM = 5e5 + 5;
constexpr int MAXN = 1.2e7 + 5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, q;
int val[MAXM], cnt;

struct FHQTreap {
    int l[MAXN], r[MAXN], rd[MAXN], v[MAXN], sz[MAXN], sum[MAXN], lz[MAXN], tot = 0, rt = 0;

    void pull(int &k) {
        sz[k] = sz[l[k]] + sz[r[k]] + 1;
        sum[k] = sum[l[k]] + sum[r[k]] + v[k];
    }

    void lazy(int &k, int x) {
        v[k] += x;
        sum[k] += x * sz[k];
        lz[k] += x;
    }

    void push(int &k) {
        if (lz[k]) {
            if (l[k])
                l[k] = copy(l[k]);
            if (r[k])
                r[k] = copy(r[k]);
            if (l[k])
                lazy(l[k], lz[k]);
            if (r[k])
                lazy(r[k], lz[k]);
            lz[k] = 0;
        }
    }

    int nw(int x) {
        v[++tot] = x;
        sz[tot] = 1;
        rd[tot] = rng();
        sum[tot] = x;
        lz[tot] = 0;
        l[tot] = r[tot] = 0;
        return tot;
    }

    int copy(int x) {
        int ans = nw(0);
        v[ans] = v[x];
        sz[ans] = sz[x];
        rd[ans] = rd[x];
        sum[ans] = sum[x];
        lz[ans] = lz[x];
        l[ans] = l[x];
        r[ans] = r[x];
        return ans;
    }

    int merge(int a, int b) {
        if (!a || !b) {
            return copy(a | b);
        }
        a = copy(a);
        b = copy(b);
        if (rd[a] < rd[b]) {
            push(a);
            r[a] = merge(r[a], b);
            pull(a);
            return a;
        } else {
            push(b);
            l[b] = merge(a, l[b]);
            pull(b);
            return b;
        }
    }

    void split(int k, int x, int &a, int &b) {
        if (k == 0) {
            a = b = 0;
            return;
        }
        k = copy(k);
        push(k);
        if (v[k] <= x) {
            a = k;
            split(r[k], x, r[k], b);
        } else {
            b = k;
            split(l[k], x, a, l[k]);
        }
        pull(k);
    }

    void split2(int k, int x, int &a, int &b) {
        if (k == 0) {
            a = b = 0;
            return;
        }
        k = copy(k);
        push(k);
        if (sz[l[k]] + 1 <= x) {
            a = k;
            split2(r[k], x - 1 - sz[l[k]], r[k], b);
        } else {
            b = k;
            split2(l[k], x, a, l[k]);
        }
        pull(k);
    }

    void dfs(int &u) {
        if (!u)
            return;
        push(u);
        dfs(l[u]);
        val[++cnt] = v[u];
        dfs(r[u]);
        pull(u);
    }

    void rebuild() {
        cnt = 0;
        dfs(rt);
        tot = rt = 0;
        for (int i = 1; i <= n; i++) {
            rt = merge(rt, nw(val[i]));
            // cerr << val[i] << endl;
        }
    }
} fhq;

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> val[i];

    fhq.rebuild();

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r, v, a, b, c;
            cin >> l >> r >> v;
            fhq.split2(fhq.rt, r, a, b);
            fhq.split2(a, l - 1, a, c);
            c = fhq.copy(c);
            fhq.lazy(c, v);
            fhq.rt = fhq.merge(fhq.merge(a, c), b);
        } else if (op == 2) {
            int l, r, x, y, a, b, c, d, e, f;
            cin >> l >> r >> x >> y;
            fhq.split2(fhq.rt, y, d, e);
            fhq.split2(d, x - 1, d, f);
            fhq.split2(fhq.rt, r, a, b);
            fhq.split2(a, l - 1, a, c);
            fhq.rt = fhq.merge(fhq.merge(a, f), b);
        } else {
            int l, r, a, b, c;
            cin >> l >> r;
            fhq.split2(fhq.rt, r, a, b);
            fhq.split2(a, l - 1, a, c);
            cout << fhq.sum[c] << endl;
            fhq.rt = fhq.merge(fhq.merge(a, c), b);
        }
        if (fhq.tot >= (int)1e7) {
            fhq.rebuild();
        }
    }

    return 0;
}