牛子题
先观察询问怎么处理，因为是棵树，直接拆 \(dis\) ，有 \(dis(p_i,x)=dis[p_i]+dis[x]-2\times dis[lca]\) ，前两项很好处理，但是对于 \(dis[lca(p_i,x)],i \in [l,r]\) 比较难处理，但是可以转化成经过这条边的次数再乘上边权，求一个点到根加1，一个点到根查询，所以树剖+主席树很好搞，然后注意空间，定期重构，多个位置没必要多次开点，还要标记永久化。
#include<bits/stdc++.h>
#define il inline
#define maxn 200003
using namespace std;
typedef long long ll;
const ll mod=1ll<<30;
il int read(){
char c;int x=0,f=0;
while(!isdigit(c=getchar()))f|=(c=='-');
while(isdigit(c))x=(x*10)+(c^48),c=getchar();
return f?-x:x;
}
struct E{
int Next,to,w;
}edge[maxn<<1];
int n,m,cnt,head[maxn],p[maxn],a[maxn],siz[maxn],fa[maxn],hson[maxn];
int dfn[maxn],num=0,rev[maxn],Top[maxn];
ll dis[maxn],sumd[maxn],pre[maxn];
int ls[38000005],rs[38000005],tag[38000005];
ll sum[38000005];
int tot,root[maxn];
il void addedge(int from,int to,int w){
edge[++cnt]={head[from],to,w};
head[from]=cnt;
}
void dfs1(int x,int FA){
fa[x]=FA,siz[x]=1;
for(int i=head[x];i;i=edge[i].Next){
int to=edge[i].to,w=edge[i].w;
if(to==FA)continue;
a[to]=w,dis[to]=dis[x]+w;
dfs1(to,x);
siz[x]+=siz[to];
if(siz[to]>siz[hson[x]])hson[x]=to;
}
}
void dfs2(int x,int u){
Top[x]=u,dfn[x]=++num,rev[num]=x;
if(!hson[x])return;
dfs2(hson[x],u);
for(int i=head[x];i;i=edge[i].Next){
int to=edge[i].to;
if(to!=hson[x]&&to!=fa[x])dfs2(to,to);
}
}
int lim;
il void pushup(int x,int lt,int rt){sum[x]=sum[ls[x]]+sum[rs[x]]+tag[x]*(pre[rt]-pre[lt-1]);}
void update(int &now,int lt,int rt,int qx,int qy){
if(now<=lim)ls[++tot]=ls[now],rs[tot]=rs[now],tag[tot]=tag[now],sum[tot]=sum[now],now=tot;
if(lt>=qx&&rt<=qy){
tag[now]++,sum[now]+=pre[rt]-pre[lt-1];
return;
}
int mid=(lt+rt)>>1;
if(qx<=mid)update(ls[now],lt,mid,qx,qy);
if(qy>mid)update(rs[now],mid+1,rt,qx,qy);
pushup(now,lt,rt);
}
il void updateR(int now,int x){
lim=tot;
while(x){
update(root[now],1,n,dfn[Top[x]],dfn[x]);
x=fa[Top[x]];
}
}
ll query(int now,int lt,int rt,int qx,int qy){
if(lt>=qx&&rt<=qy)return sum[now];
int mid=(lt+rt)>>1;
ll res=tag[now]*(pre[min(rt,qy)]-pre[max(lt,qx)-1]);
if(qx<=mid)res+=query(ls[now],lt,mid,qx,qy);
if(qy>mid)res+=query(rs[now],mid+1,rt,qx,qy);
return res;
}
il ll queryR(int p,int x){
ll res=dis[x]*p+sumd[p];
while(x){
res-=query(root[p],1,n,dfn[Top[x]],dfn[x])*2;
x=fa[Top[x]];
}
return res;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)p[i]=read();
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
addedge(u,v,w),addedge(v,u,w);
}
dfs1(1,0),dfs2(1,1);
for(int i=1;i<=n;i++)sumd[i]=sumd[i-1]+dis[p[i]],pre[i]=pre[i-1]+a[rev[i]];
for(int i=1;i<=n;i++)root[i]=root[i-1],updateR(i,p[i]);
int opt,a,b,c,os=0;
ll lstans=0;
while(m--){
opt=read(),a=lstans^read();
if(opt==1){
b=lstans^read(),c=lstans^read();
lstans=queryR(b,c)-queryR(a-1,c);
printf("%lld\n",lstans),lstans%=mod;
}
else{
sumd[a]=sumd[a]-dis[p[a]]+dis[p[a+1]],swap(p[a],p[a+1]),++os;
if(os==150000){
os=0,tot=0;
for(int i=1;i<=n;i++)root[i]=root[i-1],updateR(i,p[i]);
}else root[a]=root[a-1],updateR(a,p[a]);
}
}
return 0;
}