题解（给个赞吧）

/*
This code was automatically submitted by chhongzh's bot!

             More info: jj66amvxo[at]mozmail[dot]com
                      Submit At: 2026-05-24 20:36:13
                             Time Used: 580.600954ms

*/

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
namespace code{
inline int read(){
int a=0,b=1;char s=getchar();
while(s<48||s>57){if(s=='-'){b=-1;}s=getchar();}
while(s>=48&&s<=57)a=(a<<1)+(a<<3)+s-48,s=getchar();
return ab;
}
int n,q,C;
#define R register
const int maxn=2.5e5,B=500;
long long a[maxn+5];int c[maxn+5];
int bel[maxn+5],lc[maxn/B+5],rc[maxn/B+5],block;
int id[maxn/B+5][maxn+5],num,fa[10maxn+5],siz[10maxn+5];
long long sum[maxn/B+5],tag[10maxn+5];
int find(int x){//查询并查集时顺便下放懒标记
if(fa[x]x)return x;
int a=find(fa[x]);
if(fa[x]!=a)tag[x]+=tag[fa[x]];
return fa[x]=a;
}
__int128 ans;//答案的值域似乎大得离谱
void write(__int128 x){
if(x<0)putchar('-'),x=~x+1;
if(x>9)write(x/10);
putchar(x%10+48);
}
inline void print(__int128 x,char c){write(x),putchar(c);}
inline void main(){
n=read(),q=read(),C=read();
for(R int i=1;i<=n;i=-~i)a[i]=read();
for(R int i=1;i<=n;i=-~i)c[i]=read();
block=sqrt(n);
for(R int i=1;i<=n;i=-~i)bel[i]=(i-1)/block+1;
for(R int i=1,l=1,r;l<=n;i=-~i,l=r+1)r=min(l+block-1,n),lc[i]=l,rc[i]=r;
num=n;
for(R int i=1;i<=bel[n];i=-~i){
for(R int j=lc[i];j<=rc[i];j=-~j)sum[i]+=a[j];
for(R int j=lc[i];j<=rc[i];j=-~j){
if(!id[i][c[j]])id[i][c[j]]=++num,fa[num]=num;
fa[j]=id[i][c[j]],++siz[id[i][c[j]]];
}
}
while(q--){
int opt=read();
switch(opt){
case 1:{//合并颜色
int l=read(),r=read(),x=read(),y=read();
if(xy)break;//这里主要是为了对拍方便，不知道数据里有没有这种情况
if(bel[l]==bel[r]){
if(!id[bel[l]][x]||fa[id[bel[l]][x]]!=id[bel[l]][x])break;
++num,fa[num]=num;
if(id[bel[l]][y]&&fa[id[bel[l]][y]]id[bel[l]][y])
fa[id[bel[l]][y]]=num,siz[num]+=siz[id[bel[l]][y]];//维护子树中颜色节点的个数，便于更新答案
id[bel[l]][y]=num;
for(R int i=l;i<=r;i=-~i){
int f=find(i);a[i]+=tag[i],tag[i]=0;
if(fid[bel[i]][x])a[i]+=tag[f],fa[i]=num,++siz[num],--siz[f];
}
}
else{//为什么不将这么多重复冗长的部分用函数代替呢。。。
if(id[bel[l]][x]&&fa[id[bel[l]][x]]==id[bel[l]][x]){
++num,fa[num]=num;
if(id[bel[l]][y]&&fa[id[bel[l]][y]]id[bel[l]][y])
fa[id[bel[l]][y]]=num,siz[num]+=siz[id[bel[l]][y]];
id[bel[l]][y]=num;
for(R int i=l;i<=rc[bel[l]];i=-~i){
int f=find(i);a[i]+=tag[i],tag[i]=0;
if(fid[bel[i]][x])a[i]+=tag[f],fa[i]=num,++siz[num],--siz[f];
}
}
if(id[bel[r]][x]&&fa[id[bel[r]][x]]==id[bel[r]][x]){
++num,fa[num]=num;
if(id[bel[r]][y]&&fa[id[bel[r]][y]]id[bel[r]][y])
fa[id[bel[r]][y]]=num,siz[num]+=siz[id[bel[r]][y]];
id[bel[r]][y]=num;
for(R int i=lc[bel[r]];i<=r;i=-~i){
int f=find(i);a[i]+=tag[i],tag[i]=0;
if(fid[bel[i]][x])a[i]+=tag[f],fa[i]=num,++siz[num],--siz[f];
}
}
for(R int i=bel[l]+1;i<bel[r];i=-~i){
if(!id[i][x]||fa[id[i][x]]!=id[i][x])continue;
if(id[i][y]&&fa[id[i][y]]==id[i][y]){
++num,fa[num]=num;
fa[id[i][y]]=num,fa[id[i][x]]=num;
siz[num]+=siz[id[i][y]],siz[num]+=siz[id[i][x]];
id[i][y]=num;
}
else id[i][y]=id[i][x],id[i][x]=0;//如果y不存在，直接将x修改成y即可
}
}
break;
}
case 2:{
int l=read(),r=read(),x=read(),v=read();
if(bel[l]bel[r]){
if(!id[bel[l]][x]||fa[id[bel[l]][x]]!=id[bel[l]][x])break;
for(R int i=l;i<=r;i=-~i){
int f=find(i);a[i]+=tag[i],tag[i]=0;
if(fid[bel[i]][x])a[i]+=v,sum[bel[i]]+=v;
}
}
else{
if(id[bel[l]][x]&&fa[id[bel[l]][x]]id[bel[l]][x])
for(R int i=l;i<=rc[bel[l]];i=-~i){
int f=find(i);a[i]+=tag[i],tag[i]=0;
if(fid[bel[i]][x])a[i]+=v,sum[bel[i]]+=v;
}
if(id[bel[r]][x]&&fa[id[bel[r]][x]]id[bel[r]][x])
for(R int i=lc[bel[r]];i<=r;i=-~i){
int f=find(i);a[i]+=tag[i],tag[i]=0;
if(fid[bel[i]][x])a[i]+=v,sum[bel[i]]+=v;
}
for(R int i=bel[l]+1;i<bel[r];i=-~i)
if(id[i][x]&&fa[id[i][x]]==id[i][x])tag[id[i][x]]+=v,sum[i]+=1LL*siz[id[i][x]]*v;//这里我们直接将懒标记对整块的答案处理完了
}
break;
}
case 3:{
int l=read(),r=read();ans=0;
if(bel[l]==bel[r])
for(R int i=l;i<=r;i=-~i){
int f=find(i);a[i]+=tag[i],tag[i]=0;
ans+=a[i]+tag[f];//前面只处理的懒标记对整块的贡献
}
else{
for(R int i=l;i<=rc[bel[l]];i=-~i){
int f=find(i);a[i]+=tag[i],tag[i]=0;
ans+=a[i]+tag[f];
}
for(R int i=lc[bel[r]];i<=r;i=-~i){
int f=find(i);a[i]+=tag[i],tag[i]=0;
ans+=a[i]+tag[f];
}
for(R int i=bel[l]+1;i<bel[r];i=-~i)ans+=sum[i];
}
print(ans,'\n');
}
}
}
}
}
int main(){return code::main(),0;}