rt，思路是很普通的分块。

目前确定时间主要浪费在 clear() 和 build() 两个函数。

想问是我实现写的太烂了还是哪里复杂度假了实在不知道怎么优化了。

跟参数关系不大应该，块长从 400 到 750 试了很多依旧寄。

#include<cstdio>
const int len=700;
short bl[250001];
int n,col[250001];
long long a[250001],stg[250001];
//stg 维护加法标记 
int fa[250001],sz[250001],ver[701];
short hed[250001],net[701],tot;
int q[701],head,tail;
inline void add(int x,int y){
	ver[++tot]=y;
	net[tot]=hed[x];
	hed[x]=tot;
}
struct pts{
	int cl,cr;
	long long sum;
	int rt[250001];
	//cl cr 记录这个块对应左右端点
	//rt 记录这个块某种颜色对应森林的根节点 
	inline void clear(){
		//下放标记，更新颜色信息
		//每个森林的根节点颜色为整个森林当前颜色
		//建图后 bfs 一遍 
		int i;
		sum=tot=0;
		head=1;tail=0;
		for(i=cl;i<=cr;i++){
			rt[col[i]]=0;
			if(i!=fa[i])add(fa[i],i);
			else q[++tail]=i;
		}
		while(head<=tail){
			int x=q[head++];
			a[x]+=stg[x];
			for(i=hed[x];i;i=net[i]){
				int y=ver[i];
				col[y]=col[x];
				stg[y]+=stg[x];
				q[++tail]=y;
			}
			stg[x]=hed[x]=0;
		}
	}
	inline void build(){
		int i;
		for(i=cl;i<=cr;i++)fa[i]=i,sz[i]=1,sum+=a[i];
		for(i=cl;i<=cr;i++){
			if(!rt[col[i]])rt[col[i]]=i;
			else fa[i]=rt[col[i]],sz[rt[col[i]]]++;
		}
	}
	inline void merge(int x,int y){
		if(!rt[x])return;
		if(!rt[y]){
			rt[y]=rt[x];rt[x]=0;
			col[rt[y]]=y;
			return;
		}
		fa[rt[x]]=rt[y];
		sz[rt[y]]+=sz[rt[x]];
		stg[rt[x]]-=stg[rt[y]];
		rt[x]=0;
	}
	inline void change(int x,int v){
		sum+=1ll*v*sz[rt[x]];
		stg[rt[x]]+=v;
	}
}bk[401];
inline int read(){
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x;
}
int main(){
	int i,j,q,c;
	n=read();q=read();c=read();
	for(i=1;i<=n;i++)a[i]=read();
	for(i=1;i<=n;i++)col[i]=read();
	for(i=1;i<=n;i++)bl[i]=(i-1)/len+1;
	for(i=1;i<=bl[n];i++){
		bk[i].cl=(i-1)*len+1;
		bk[i].cr=i*len;
		if(bk[i].cr>n)bk[i].cr=n;
		bk[i].build();
	}
	while(q--){
		int op,l,r,x,y;
		op=read();l=read();r=read();
		if(op!=3)x=read(),y=read();
		int lp=bl[l],rp=bl[r];
		bk[lp].clear();if(lp!=rp)bk[rp].clear();
		if(op==1){
			if(lp==rp){for(i=l;i<=r;i++)if(col[i]==x)col[i]=y;}
			else{
				for(i=lp+1;i<=rp-1;i++)bk[i].merge(x,y);
				for(i=l;i<=bk[lp].cr;i++)if(col[i]==x)col[i]=y;
				for(i=r;i>=bk[rp].cl;i--)if(col[i]==x)col[i]=y;
			}
		}
		else if(op==2){
			if(lp==rp){for(i=l;i<=r;i++)if(col[i]==x)a[i]+=y;}
			else{
				for(i=lp+1;i<=rp-1;i++)bk[i].change(x,y);
				for(i=l;i<=bk[lp].cr;i++)if(col[i]==x)a[i]+=y;
				for(i=r;i>=bk[rp].cl;i--)if(col[i]==x)a[i]+=y;
			}
		}
		else{
			long long res=0;
			if(lp==rp)for(i=l;i<=r;i++)res+=a[i];
			else{
				for(i=lp+1;i<=rp-1;i++)res+=bk[i].sum;
				for(i=l;i<=bk[lp].cr;i++)res+=a[i];
				for(i=r;i>=bk[rp].cl;i--)res+=a[i];
			}
			printf("%lld\n",res);
		}
		bk[lp].build();if(lp!=rp)bk[rp].build();
	}
}