自动搬运

查看原文

来自洛谷，原作者为

	seika27 1.048596%||秋风扫落叶||哦对了朋友们我已经退役了||R95853||SR6G5-R3XA

搬运于2025-08-24 23:13:36，当前版本为作者最后更新于2025-04-15 15:32:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

这是一道非常有趣的题目，可以用很多种方法解决。

我在这里提供一种 FHQ-treap 的做法。

我们发现这道题只有一种操作，就是将一个序列 $A$ 中所有的 $l\leq A_i \leq r$ 全部改为 $k$。

那么我们将这个操作分为三部分。

第一步在我们的 FHQ-treap 上分裂出 $x<l$，$l\leq x\leq r$，$r<x$ 这三部分。这一步非常简单，是基本操作，同时，我们令分裂出来三部分的根节点分别为 $sx$，$sy$，$sz$。

第二步合并 $sx$ 和 $sz$，这一步相当与删除了 $sy$。

第三步，往我们的 FHQ-treap 中塞入 $siz_{sy}$ 个 $k$。我们知道，原本 FHQ-treap 中，同一个数是不会在同一个节点的。但是在这里，我们考虑给每个节点多一个 $cnt$ 值。表示这个节点拥有 $cnt$ 个值为 $val$的数字。

既然如此，在 push_up 中 $siz$ 的更新就会变成 $siz_x=siz_ {ls}+siz_{rs}+cnt_x$。

既然是统计和，所以维护 $sum$ 是显然的。

接下来我们探讨一个问题，我们根据 $l$ 和 $r$ 进行分裂，最后却插入的是 $k$。会不会打破左小右大的规则呢。

答案是不会，这里关键就在于我们是先把 $sx$ 和 $sz$ 合并了，然后在合并完的 FHQ-treap 上重新做了一次普通的插入操作。这样我们就不用担心会出现上文所述的问题了。

代码不是很好，请见谅。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
const int N=7e5+5;
struct fhqarr{int ls,rs,val,cnt,rnd,siz,sum;};
struct fhqtreap
{
	fhqarr b[N];
	int tot;
	int rt;
	int sx,sy,sz;
	inline int newnode(int x,int res)
	{
		b[++tot].val=x;
		b[tot].cnt=res;
		b[tot].sum=x*res;
		b[tot].rnd=rand();
		b[tot].siz=res;
		return tot;
	}
	inline void up(int x)
	{
		b[x].siz=b[b[x].ls].siz+b[b[x].rs].siz+b[x].cnt;
		b[x].sum=b[b[x].ls].sum+b[b[x].rs].sum+b[x].cnt*b[x].val;
		return;
	}
	void split(int x,int k,int &u,int &v)
	{
		if(!x){u=v=0;return;}
		if(b[x].val<=k)u=x,split(b[x].rs,k,b[x].rs,v);
		else v=x,split(b[x].ls,k,u,b[x].ls);
		up(x);
	}
	int merge(int x,int y)
	{
		if(!x||!y)return x+y;
		if(b[x].rnd<b[y].rnd)
		{
			b[x].rs=merge(b[x].rs,y);
			up(x);
			return x;
		}
		else 
		{
			b[y].ls=merge(x,b[y].ls);
			up(y);
			return y;
		}
	}
	inline void insert(int v,int p)
	{
		split(rt,v,sx,sy);
		rt=merge(merge(sx,newnode(v,p)),sy);
		return;
	}
	inline void update(int l,int r,int k)
	{
		split(rt,r,sx,sz);
		split(sx,l-1,sx,sy);
		int slv=b[sy].siz;
		rt=merge(sx,sz);
		insert(k,slv);
		return;
	}
}momoka;
signed main()
{
	srand(time(0));
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>q;
	for(int i=1,x;i<=n;++i)cin>>x,momoka.insert(x,1);
	cout<<momoka.b[momoka.rt].sum<<'\n';
	while(q--)
	{
		int l,r,k;
		cin>>l>>r>>k;
		momoka.update(l,r,k);
		cout<<momoka.b[momoka.rt].sum<<'\n';
	}
	return 0;
}