Description

给出一棵带权有根树，要求： 1. 树上的路径区间加 2. 树上路径区间查询和 3. 树上路径整体旋转一位（如：原路径上的权值依次是这样的：1,2,3,4，操作完后变成：4,1,2,3）

n<=100000 时限：2S

Solution

这显然是链剖套Splay嘛， 旋转就相当于删掉最后一个，加到前面去，

听说LCT更简单

复杂度： O(nlog(n))

Code

#include <iostream> #include <cstdio> #include <cstdlib> #define fo(i,a,b) for(int i=a;i<=b;i++) #define efo(i,q) for(int i=A[q];i;i=B[i][0]) using namespace std; typedef long long LL; const int N=100500; int read(int &n) { char ch=' ';int q=0,w=1; for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar()); if(ch=='-')w=-1,ch=getchar(); for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n; } int m,n,ans; int B[2*N][2],A[N],B0; struct qqww { int fa,lt,zx,si,c; }a[N]; struct qwqw { int l,r,fa,si,la; LL v,sum; }b[N]; int root,b0; void link(int q,int w) { B[++B0][0]=A[q];A[q]=B0,B[B0][1]=w; B[++B0][0]=A[w];A[w]=B0,B[B0][1]=q; } int dfsf(int q,int fa,int c) { a[q].fa=fa,a[q].si=1;a[q].c=c; efo(i,q)if(B[i][1]!=fa)a[q].si+=dfsf(B[i][1],q,c+1); return a[q].si; } void dfs(int q,int fa,int lt) { a[q].lt=(lt?lt:lt=q); a[q].zx=++b0; int mx=0; efo(i,q)if(B[i][1]!=fa)if(a[mx].si<a[B[i][1]].si)mx=B[i][1]; if(mx)dfs(mx,q,lt); efo(i,q)if(B[i][1]!=fa&&B[i][1]!=mx)dfs(B[i][1],q,0); } bool SD(int q){return q==b[b[q].fa].r;} void merge(int q) { b[q].si=b[b[q].l].si+1+b[b[q].r].si; b[q].sum=b[b[q].l].sum+b[q].v+b[b[q].r].sum; } void doit(int q) { if(!b[q].la)return; b[q].v+=b[q].la; b[q].sum+=(LL)b[q].si*(LL)b[q].la; if(b[q].l)b[b[q].l].la+=b[q].la; if(b[q].r)b[b[q].r].la+=b[q].la; b[q].la=0; } void rotate(int q) { int t=b[q].fa; if(!SD(q)) { b[t].l=b[q].r; b[b[q].r].fa=t; b[q].r=t; }else { b[t].r=b[q].l; b[b[q].l].fa=t; b[q].l=t; } if(SD(t))b[b[t].fa].r=q; else b[b[t].fa].l=q; b[q].fa=b[t].fa; b[t].fa=q; merge(t); merge(q); b[0].l=b[0].r=b[0].fa=0; } int Splay(int q,int T) { while(b[q].fa!=T) { if(b[b[q].fa].fa!=T) if(SD(q)==SD(b[q].fa))rotate(b[q].fa); else rotate(q); rotate(q); } if(!T)root=q; } int search(int q,int w) { doit(b[q].l),doit(b[q].r); if(b[b[q].l].si>=w)return search(b[q].l,w); w-=b[b[q].l].si+1; if(!w)return q; return search(b[q].r,w); } void changea(int q,int w,int e) { Splay(search(root,q-1),0); Splay(w=search(root,w+1),root); b[b[w].l].la+=e; doit(b[w].l); merge(w),merge(root); } LL Gsum(int q,int w) { Splay(search(root,q-1),0); Splay(w=search(root,w+1),root); return b[b[w].l].sum; } int DLT(int q) { Splay(search(root,q-1),0); Splay(q=search(root,q+1),root); int ans=b[q].l; b[b[q].l].fa=0;b[q].l=0; merge(q),merge(root); return ans; } void IST(int q,int w) { Splay(search(root,q),0); b[w].l=0;b[w].r=b[root].r;b[w].fa=root; b[root].r=w;if(b[w].r)b[b[w].r].fa=w; merge(w),merge(root); } void SWAP_v(int q,int w) { if(q>w)swap(q,w); Splay(q=search(root,q),0); Splay(w=search(root,w),root); swap(b[q].v,b[w].v); merge(w),merge(q); } void modifya(int q,int w,int e) { while(a[q].lt!=a[w].lt) { if(a[a[q].lt].c<a[a[w].lt].c)swap(q,w); int t=a[q].lt; changea(a[t].zx,a[q].zx,e); q=a[t].fa; } if(a[q].c<a[w].c)swap(q,w); changea(a[w].zx,a[q].zx,e); } LL find(int q,int w) { LL ans=0; while(a[q].lt!=a[w].lt) { if(a[a[q].lt].c<a[a[w].lt].c)swap(q,w); int t=a[q].lt; ans+=Gsum(a[t].zx,a[q].zx); q=a[t].fa; } if(a[q].c<a[w].c)swap(q,w); return ans+Gsum(a[w].zx,a[q].zx); } int c1[N][2],c2[N][2],c10,c20; void change_shift(int q,int w) { if(q==w)return; swap(q,w);c10=c20=0; while(a[q].lt!=a[w].lt) { if(a[a[q].lt].c>a[a[w].lt].c)c1[++c10][0]=q,c1[c10][1]=a[q].lt,q=a[a[q].lt].fa; else c2[++c20][1]=w,c2[c20][0]=a[w].lt,w=a[a[w].lt].fa; } if(a[q].c>a[w].c)c1[++c10][0]=q,c1[c10][1]=w; else c2[++c20][1]=w,c2[c20][0]=q; q=w=0; fo(i,1,c10) { q=c1[i][0],w=c1[i][1]; int q1=DLT(a[q].zx); IST(a[w].zx-1,q1); if(i!=c10)SWAP_v(a[w].zx,a[c1[i+1][0]].zx); } int t=w; for(;c20;c20--) { q=c2[c20][0],w=c2[c20][1]; if(t)SWAP_v(a[t].zx,a[q].zx); int q1=DLT(a[q].zx); IST(a[w].zx-1,q1); t=w; } } int main() { freopen("shift.in","r",stdin); freopen("shift.out","w",stdout); int q,w,e; read(n); fo(i,1,n-1)read(q),read(w),link(q,w); dfsf(1,0,1); b0=root=1; dfs(1,0,0); fo(i,1,n+1)b[i].r=i+1,b[i+1].fa=i,b[i].si=n+2-i+1; b[n+2].si=1;b0++; read(m); fo(i,1,m) { char ch=' '; while(ch<'A'||ch>'Z')ch=getchar(); if(ch=='A') { read(q),read(w),read(e); modifya(q,w,e); }else if(ch=='S') { read(q),read(w); change_shift(q,w); }else { read(q),read(w); printf("%lld\n",find(q,w)); } } return 0; }