题解：P8659 [蓝桥杯 2017 国 A] 数组操作

__An · 2025-07-21 16:04:47 · 题解

FHQ_Treap ！！！

前置知识 FHQ_Treap。

题意简述

有一个长度为 n 序列 A ，需要你维护三个操作：

• 1 l r d 对于 l \le i \le r ，执行 a_i = a_i + d 。
• 2 l1 r1 l2 r2 将区间 [l_2,r_2] 的值复制到 [l_1,r_1] 。
• 3 l r 求 \sum_{i = l} ^ r a_i 。

  思路

  看到区间，立马联想到以合并与分裂为主要操作的 FHQ_Treap。

操作 1： 先截出序号小于等于 r 的子树，再截出序号大于 l - 1 的子树，即截出区间 [l, r] ，截出后打上懒标记即可，最后记得将原树合并回去。

inline void update(int l, int r, int k) {
    int x, y, z;
    split(rt, r, x, z);
    split(x, l - 1, x, y);
    y = copy(y);
    push_add(y, k);
    rt = merge(x, merge(y, z));
}

操作 2： 容易发现我们只需要复制 [l2, r2] 这一区间，直接将 [l1, r1] 丢掉即可。因为要区间复制，因此考虑可持久化，每次修改前将原节点复制出来。

由于区间可能重叠，因此先将 [l2, r2] 复制出来，合并回去，再截出 [l1, r1] 直接替换，再次合并回去。

inline void paste(int l1, int r1, int l2, int r2) {
    int L, R, M, d, e;
    split(rt, r2, L, R);
    split(L, l2 - 1, L, M);
    d = copy(M);
    rt = merge(L, merge(M, R));
    split(rt, r1, L, R);
    split(L, l1 - 1, L, M);
    t[M] = t[d];
    rt = merge(L, merge(M, R));
    return;
}

操作 3： 同操作 1，先截出区间 [l, r] ，随后直接查询即可，记得下传懒标记。

inline int query(int l, int r) {
    int x, y, z, res;
    split(rt, r, x, z);
    split(x, l - 1, x, y);
    res = t[y].sum;
    rt = merge(x, merge(y, z));
    return res;
}

注意

可持久化 FHQ_Treap 会复制出大量节点导致内存超限，因此我们要设置一个阈值，每次节点数超过该值时，直接重构即可，这里设的阈值为 800000。

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define mp(a, b) make_pair(a, b)
#define pr pair<int, int>
#define pb push_back
#define iosfst ios::sync_with_stdio(false);cin.tie(0), cout.tie(0)
using namespace std;
namespace An{
    const int maxn = 1e6+5;
    int n, m, num;
    int tmp[maxn];
    namespace fhq_treap{
        int cnt, rt;
        struct node{
            int lc, rc, sum, val, siz, rnd, add, tag, rev;
        }t[maxn];
        inline int new_node(int x=0) {
            int u = ++cnt;
            t[u].val = t[u].sum = x;
            t[u].siz = 1;
            t[u].tag = -1;
            t[u].add = 0;
            t[u].rnd = rand();
            return u;
        }
        inline int copy(int x) {
            int u = ++cnt;
            t[u] = t[x];
            return u;
        }
        inline void pushup(int x) {
            t[x].siz = t[t[x].lc].siz + t[t[x].rc].siz + 1;
            t[x].sum = t[t[x].lc].sum + t[t[x].rc].sum + t[x].val;
        }
        inline void push_add(int x, int k) {
            t[x].add = t[x].add + k;
            t[x].val = t[x].val + k;
            t[x].sum = t[x].sum + t[x].siz * k;
        }
        inline void pushdown(int x) {
            if(!t[x].add) return ;
            if(t[x].lc) t[x].lc = copy(t[x].lc);
            if(t[x].rc) t[x].rc = copy(t[x].rc);
            if(t[x].add) {
                if(t[x].lc) push_add(t[x].lc, t[x].add);
                if(t[x].rc) push_add(t[x].rc, t[x].add);
                t[x].add = 0;
            }
        }
        int merge(int x, int y) {
            if(!x || !y) return x | y;
            if(t[x].rnd < t[y].rnd) {
                pushdown(x);x = copy(x);
                t[x].rc = merge(t[x].rc, y);
                pushup(x);
                return x;
            }
            else {
                pushdown(y);y = copy(y);
                t[y].lc = merge(x, t[y].lc);
                pushup(y);
                return y;
            }
        }
        void split(int tmp,int k,int &u,int &v) {
            if(!tmp) {
                u = v = 0;
                return;
            }
            pushdown(tmp);
            if(t[t[tmp].lc].siz < k) {
                u = copy(tmp);
                split(t[u].rc, k - t[t[tmp].lc].siz - 1, t[u].rc, v);
                pushup(u);
            }
            else {
                v = copy(tmp);
                split(t[v].lc, k, u, t[v].lc);
                pushup(v);
            }
        }
        inline void update(int l, int r, int k) {
            int x, y, z;
            split(rt, r, x, z);
            split(x, l - 1, x, y);
            y = copy(y);
            push_add(y, k);
            rt = merge(x, merge(y, z));
        }
        inline int query(int l, int r) {
            int x, y, z, res;
            split(rt, r, x, z);
            split(x, l - 1, x, y);
            res = t[y].sum;
            rt = merge(x, merge(y, z));
            return res;
        }
        inline void paste(int l1, int r1, int l2, int r2) {
            int L, R, M, d, e;
            split(rt, r2, L, R);
            split(L, l2 - 1, L, M);
            d = copy(M);
            rt = merge(L, merge(M, R));
            split(rt, r1, L, R);
            split(L, l1 - 1, L, M);
            t[M] = t[d];
            rt = merge(L, merge(M, R));
            return;
        }
        void dfs(int const &x) {
            pushdown(x);
            if(t[x].lc) dfs(t[x].lc);
            tmp[++num] = t[x].val;
            if(t[x].rc) dfs(t[x].rc);
        }
        int build(int l,int r) {
            if(l > r) return 0;
            int mid = l + r >> 1;
            int x = new_node(tmp[mid]);
            t[x].lc = build(l,mid-1);
            t[x].rc = build(mid+1,r);
            pushup(x);
            return x;
        }
        inline void rebuild() {
            num = 0;dfs(rt);cnt = 0;
            rt = build(1, num);
        }
        void debug() {
            int x,y,z;
            rep (i, 1, n) {
                split(rt, i, x, z);
                split(x, i - 1, x, y);
                cout << t[y].val << '\n';
                rt = merge(x, merge(y, z));
            }
            puts("");
        }
    }
    using namespace fhq_treap;
    void work() {
        iosfst;
        srand(time(0));
        int opt, l1, l2, r1, r2, v, lst = 0;
        cin >> opt >> n >> m;
        rep (i, 1, n) cin >> tmp[i];
        rt = build(1, n);
        rep (i, 1, m) {
            cin >> opt >> l1 >> r1;
            switch(opt) {
                case 1:{
                    cin >> v;
                    update(l1, r1, v);
                    break;
                }
                case 2:{
                    cin >> l2 >> r2;
                    paste(l1, r1, l2, r2);
                    break;

                }
                case 3:{
                    cout << query(l1, r1) << '\n';
                    break;
                }
            }
            if(cnt > 800000) rebuild();
        }
    }
}
signed main() {
    An::work();
    return 0;
}