自动搬运

查看原文

来自洛谷，原作者为

	yuguanchen2022 于现实与超实中徘徊的灵魂 / 于幸存与苟存中湮灭的躯体

搬运于2025-08-24 22:41:10，当前版本为作者最后更新于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;
}