【CF757G】Can Bash Save the Day?
题意：给你一棵n个点的树和一个排列${p_i}$，边有边权。有q个操作：
1 l r x：询问$\sum\limits_{i=l}^r dist(p_i,x)$
2 x：$swap(a_x,a_{x+1})$
$n,q\le 2\times 10^5$，强制在线。
题解：学到了新姿势：可持久化点分树。我们先将询问变成前缀相减的形式，然后对于每一个前缀都用一个点分树来维护，不难在$O(\log n)$的时间内处理掉一组询问。现在问题在于如何构建可持久化点分树。
首先，点分树的深度是$O(\log n)$的，所以我们在加入一个新点的时候可以新建这个点到根的那条链。而对于2操作，我们只需要重新构建第x棵点分树就好了。但是有一个问题，我们再新建一个点的时候需要复制这个点所有儿子的信息，但是一个点的儿子数量是$O(n)$级别的，怎么办？
这就需要我们对原树进行预处理，将多叉树转变为二叉树。具体方法：假如点x的儿子分别为$c_1,c_2,...c_k$，则我们新建k-2个点$t_1,t_2...t_{k-2}$，连边：$x-t_1,t_1-t_2,...,t_{k-3}-t_{k-2}$，$c_1-x,c_2-t_1,c_3-t_2,...c_{k-1}-t_{k-2},c_k-t_{k-2}$即可。总新建的点数显然不超过n。
那么我们在点分树上的每个点最多就只有3个儿子了。再记录一下从根走到每个点的路径就很容易处理了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=200010;
typedef long long ll;
int n,m,N,cnt,Cnt,msk,mn,tot,root;
ll ans;
int to[maxn<<2],nxt[maxn<<2],head[maxn<<1],val[maxn<<2],To[maxn<<1],Nxt[maxn<<1],Head[maxn],Val[maxn<<1];
int p[maxn],siz[maxn<<1],Log[maxn<<2],d[maxn],vis[maxn<<1],dep[maxn<<1],pos[maxn<<1],rt[maxn];
ll md[20][maxn<<2],des[maxn<<1];
vector<int> step[maxn<<1];
struct node
{
int ch[3],cnt,org; ll s1,s2;
}s[maxn*60];
inline void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,nxt[cnt]=head[a],head[a]=cnt++;
}
inline void Add(int a,int b,int c)
{
To[Cnt]=b,Val[Cnt]=c,Nxt[Cnt]=Head[a],Head[a]=Cnt++;
}
void dfs1(int x,int fa)
{
for(int i=Head[x],last=0,tmp=0;i!=-1;i=Nxt[i]) if(To[i]!=fa)
{
tmp++;
if(tmp==1) add(x,To[i],Val[i]),add(To[i],x,Val[i]),last=x;
else if(tmp==d[x]-(x!=1)) add(last,To[i],Val[i]),add(To[i],last,Val[i]);
else
{
N++,add(last,N,0),add(N,last,0),last=N;
add(N,To[i],Val[i]),add(To[i],N,Val[i]);
}
}
for(int i=Head[x];i!=-1;i=Nxt[i]) if(To[i]!=fa) dfs1(To[i],x);
}
void dfs2(int x,int fa)
{
md[0][++pos[0]]=des[x],pos[x]=pos[0];
for(int i=head[x];i!=-1;i=nxt[i]) if(to[i]!=fa) des[to[i]]=des[x]+val[i],dfs2(to[i],x),md[0][++pos[0]]=des[x];
}
void getrt(int x,int fa)
{
siz[x]=1;
int tmp=0,i;
for(i=head[x];i!=-1;i=nxt[i]) if(!vis[to[i]]&&to[i]!=fa)
{
getrt(to[i],x),siz[x]+=siz[to[i]],tmp=max(tmp,siz[to[i]]);
}
tmp=max(tmp,tot-siz[x]);
if(tmp<mn) mn=tmp,root=x;
}
void solve(int x)
{
vis[x]=1,s[x].org=x;
for(int i=head[x];i!=-1;i=nxt[i]) if(!vis[to[i]])
{
tot=siz[to[i]],mn=1<<30,getrt(to[i],x),dep[root]=dep[x]+1;
for(int j=0;j<dep[x];j++) step[root].push_back(step[x][j]);
if(!s[x].ch[0]) s[x].ch[0]=root,step[root].push_back(0);
else if(!s[x].ch[1]) s[x].ch[1]=root,step[root].push_back(1);
else s[x].ch[2]=root,step[root].push_back(2);
solve(root);
}
}
inline ll lca(int a,int b)
{
a=pos[a],b=pos[b];
if(a>b) swap(a,b);
int k=Log[b-a+1];
return min(md[k][a],md[k][b-(1<<k)+1]);
}
inline ll dis(int a,int b)
{
return des[a]+des[b]-2*lca(a,b);
}
void insert(int x,int &y,int a,int b,int fa)
{
y=++tot;
int z=s[x].org;
memcpy(s[y].ch,s[x].ch,sizeof(s[y].ch)),s[y].org=z;
s[y].cnt=s[x].cnt+b,s[y].s1=s[x].s1+b*dis(z,a),s[y].s2=s[x].s2;
if(fa) s[y].s2+=b*dis(s[fa].org,a);
if(s[y].org==a) return ;
insert(s[x].ch[step[a][dep[z]]],s[y].ch[step[a][dep[z]]],a,b,y);
}
ll find(int x,int y)
{
int i,u;
ll ret=0;
for(i=0;i<dep[y];i++)
{
u=s[x].ch[step[y][i]];
ret+=(s[x].cnt-s[u].cnt)*dis(s[x].org,y)+(s[x].s1-s[u].s2);
x=u;
}
return ret+s[x].s1;
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
//freopen("cf757G.in","r",stdin);
N=n=rd(),m=rd(),msk=(1<<30)-1;
int i,j,a,b,c;
for(i=1;i<=n;i++) p[i]=rd();
memset(head,-1,sizeof(head)),memset(Head,-1,sizeof(Head));
for(i=1;i<n;i++) a=rd(),b=rd(),c=rd(),Add(a,b,c),Add(b,a,c),d[a]++,d[b]++;
dfs1(1,0),dfs2(1,0);
for(i=2;i<=pos[0];i++) Log[i]=Log[i>>1]+1;
for(j=1;(1<<j)<=pos[0];j++) for(i=1;i+(1<<j)-1<=pos[0];i++) md[j][i]=min(md[j-1][i],md[j-1][i+(1<<(j-1))]);
tot=N,mn=1<<30,getrt(1,0),rt[0]=root,solve(root);
tot=N;
for(i=1;i<=n;i++)
insert(rt[i-1],rt[i],p[i],1,0);
for(i=1;i<=m;i++)
{
if(rd()==1)
{
a=rd()^ans,b=rd()^ans,c=rd()^ans;
ans=find(rt[b],c)-find(rt[a-1],c);
printf("%lld\n",ans);
ans&=msk;
}
else
{
a=rd()^ans;
insert(rt[a-1],rt[a],p[a],0,0),swap(p[a],p[a+1]),insert(rt[a],rt[a],p[a],1,0);
}
}
return 0;
}//5 5 4 5 1 3 2 4 2 4 1 3 9 4 1 4 4 5 2 1 1 5 4 1 22 20 20 2 38 2 39 1 36 38 38