分块，时间复杂度不是 $O (q\sqrt(n))$吗qwq
求调

#include<bits/stdc++.h>
using namespace std;

namespace acac
{

	int col[510][250010];
	int fa[250010],dcol[250010],fk[250010],bcj_s[250010],tag[250010];
	//bool use[250010];
	long long val[250010],szk[250010];
	int belong(int u)
	{
		if(fa[u]!=u)return fa[u]=belong(fa[u]);
		return u;
	}
	void merge(int a,int b)
	{
		int al=belong(a),bl=belong(b);
		if(al==bl)return ;
		fa[al]=bl;
		bcj_s[bl]+=bcj_s[al];	
	}
	long long find(int u)
	{
		if(fa[u]!=u)return tag[u]+find(u);
		return tag[u];
	}
	
	int main()
	{
		int n,q,C,sz;
		scanf("%d%d%d",&n,&q,&C);
		sz=sqrt(n);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&val[i]);
			fa[i]=i;
			bcj_s[i]=1;
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&dcol[i]);
		}
		int w=1,num=0;
		for(int i=1;i<=n;i++)
		{
			num++;
			if(num>sz)
			{
				w++;
				num-=sz;
			}
			fk[i]=w;
			szk[w]+=val[i];
			if(!col[w][dcol[i]])col[w][dcol[i]]=i;
			else merge(i,col[w][dcol[i]]);
		}
		while(q--)
		{
			int op,l,r,x;
			long long v;
			scanf("%d",&op);
			if(op==1)
			{
				scanf("%d%d%d%lld",&l,&r,&x,&v);
			
				for(int i=1;i<=n;i+=sz)
				{
					if(i>=l&&min(i+sz-1,n)<=r)
					{
						
						if(!col[fk[i]][x])continue;
						if(!col[fk[i]][v])
						{
							col[fk[i]][v]=col[fk[i]][x];
							dcol[col[fk[i]][x]]=v;
							col[fk[i]][x]=0;
						}
						else 
						{ 
							merge(col[fk[i]][x],col[fk[i]][v]);
							col[fk[i]][x]=0;
						} 
					}
					else if(i>=l||min(i+sz-1,n)<=r)
					{
						int end=min(i+sz-1,r);
						for(int j=i;j<=end;j++)
						{
							bcj_s[j]=1;
							val[j]+=find(j);
							//szk[fk[j]]+=find(j);
							col[fk[j]][dcol[j]]=0;
							if(l<=j&&j<=r&&dcol[j]==x)dcol[j]=v;
						}
						for(int j=i;j<=end;j++)
						{
							
							fa[i]=i;
							tag[i]=0;
						}
						for(int j=i;j<=end;j++)
						{
							if(!col[fk[j]][dcol[j]])col[fk[j]][dcol[j]]=i;
							else merge(i,col[fk[j]][dcol[j]]);
						}
						
					}
					
				}	
			}
			else if(op==2)
			{
				scanf("%d%d%d%lld",&l,&r,&x,&v);
			
				for(int i=1;i<=n;i+=sz)
				{
					if(i>=l&&min(i+sz-1,n)<=r)
					{
						
						if(!col[fk[i]][x])continue;
						tag[col[fk[i]][x]]+=v;
						szk[fk[i]]+=v*bcj_s[col[fk[i]][x]];
					}
					else if(i>=l||min(i+sz-1,n)<=r)
					{
						int end=min(i+sz-1,r);
						for(int j=i;j<=end;j++)
						{
							if(l<=j&&j<=r&&dcol[j]==x)
							{
								szk[fk[j]]+=v;
								val[j]+=v;
							}
						}
					
						
					}
					
				}	
			}
			else
			{
				scanf("%d%d",&l,&r);
				long long ans=0;
				for(int i=1;i<=n;i+=sz)
				{
					if(i>=l&&min(i+sz-1,n)<=r)ans+=szk[fk[i]];
					else if(i>=l||min(i+sz-1,n)<=r)
					{
						int end=min(i+sz-1,r);
						for(int j=i;j<=end;j++)
						{
							if(l<=j&&j<=r)
							{
								ans+=val[j]+find(j);
							}
						}
						//cout<<dcol[2]<<endl;
						
					}
					
				}
				cout<<ans<<'\n';	
			}
		}
		return 0;
	}
}

int main()
{
	acac::main();
	return 0;
}