自动搬运

查看原文

来自洛谷，原作者为

	gxy001 ......

搬运于2025-08-24 22:38:24，当前版本为作者最后更新于2022-05-19 14:59:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

看到这题首先考虑分块，考虑如何维护这些操作。

先考虑整块操作如何处理，考虑对每块维护出一个多叉森林结构，叶子节点既是每个位置，初始时同种颜色的位置拥有同一个父节点。

合并两种颜色时，如果一种颜色原本不存在于该块内，则不用新建节点；否则新建一个节点，并将这两种颜色节点的父亲设置为新建的节点，这个新节点就代表合并后的颜色。这样维护出的森林，每个非叶子节点都有至少 $2$ 个儿子，节点个数不会超过二倍的叶子节点数。

加 $v$ 的时候只要在对应颜色的节点上打标记就好，顺便根据这个颜色的数量维护整块的答案。

对于散块，我们可以直接暴力下放标记，然后暴力维护操作，统计答案，重构森林。

时间复杂度 $O(n+q(B+\frac nB))=O(n+q\sqrt n)$。

#include<fstream>
#include<algorithm>
std::ifstream cin("military.in");
std::ofstream cout("military.out");
int const B=500;
int n,q,m,a[250010],c[250010],op[250010],ql[250010],qr[250010],qx[250010],qy[250010];
int fa[250010],f[1010],sz[1010],col[1010];
long long v[1010],sum,ans[250010];
int main(){
	cin>>n>>q>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=q;i++){
		cin>>op[i]>>ql[i]>>qr[i];
		if(op[i]!=3) cin>>qx[i]>>qy[i];
	}
	int cnt=0;
	for(int l=1,r;l<=n;l=r+1){
		r=std::min(n,l+B-1);
		for(int i=1;i<=m;i++) fa[i]=0;
		for(int i=l;i<=r;i++) v[i-l+1]=a[i],col[i-l+1]=c[i];
		sum=0;
		int len=r-l+1;
		for(int i=len+1;i<=cnt;i++) f[i]=v[i]=0;
		cnt=len;
		for(int i=1;i<=len;i++) f[i]=0,sum+=v[i],sz[i]=1;
		for(int i=1;i<=len;i++) if(!fa[col[i]]) fa[col[i]]=i;
		else{
			int u=fa[col[i]];
			if(u<=len) f[u]=fa[col[i]]=++cnt,u=f[u],sz[u]=1,col[u]=col[i];
			f[i]=u,++sz[u];
		}
		for(int i=1;i<=q;i++)
			if(ql[i]<=l&&r<=qr[i]){
				if(op[i]==1){
					if(qx[i]==qy[i]||!fa[qx[i]]);
					else if(!fa[qy[i]]){
						col[fa[qy[i]]=fa[qx[i]]]=qy[i];
						fa[qx[i]]=0;
					}else{
						int u=++cnt;
						f[fa[qy[i]]]=f[fa[qx[i]]]=u,col[u]=qy[i];
						sz[u]=sz[fa[qy[i]]]+sz[fa[qx[i]]];
						fa[qy[i]]=u,fa[qx[i]]=0;
					}
				}else if(op[i]==2){
					if(fa[qx[i]]) v[fa[qx[i]]]+=qy[i],sum+=1ll*sz[fa[qx[i]]]*qy[i];
				}else{
					ans[i]+=sum;
				}
			}else if(std::max(ql[i],l)<=std::min(qr[i],r)){
				for(int j=cnt;j;j--) if(f[j]) v[j]+=v[f[j]],col[j]=col[f[j]];
				for(int j=len+1;j<=cnt;j++) f[j]=v[j]=0;
				cnt=len;
				for(int j=1;j<=len;j++) fa[col[j]]=0,f[j]=0;
				int pl=std::max(ql[i],l)-l+1,pr=std::min(qr[i],r)-l+1;
				if(op[i]==1){
					for(int o=pl;o<=pr;o++) if(col[o]==qx[i]) col[o]=qy[i];
				}else if(op[i]==2){
					for(int o=pl;o<=pr;o++) if(col[o]==qx[i]) v[o]+=qy[i],sum+=qy[i];
				}else{
					for(int o=pl;o<=pr;o++) ans[i]+=v[o];
				}
				for(int j=1;j<=len;j++) if(!fa[col[j]]) fa[col[j]]=j;
				else{
					int u=fa[col[j]];
					if(u<=len) f[u]=fa[col[j]]=++cnt,u=f[u],sz[u]=1,col[u]=col[j];
					f[j]=u,++sz[u];
				}
			}
	}
	for(int i=1;i<=q;i++) if(op[i]==3) cout<<ans[i]<<'\n';
	return 0;
}