[BZOJ3159]决战（树链剖分+Splay）

=== ===

这里放传送门

=== ===

题解

树链增加一个值，树链求和求最大最小值？似乎要用链剖啊 但是这个翻转操作是什么鬼链剖不一般都是搭配线段树食用的么→_→ 好吧强行套上平衡树 方法蠢到家了，就是把要翻转的那一条链一块块揪出来按顺序拼成一大棵Splay然后打上翻转标记再一块块塞会原来的地方。。 不过这个题目的一个方便之处就是翻转操作一定是到根的一条路径，所以它保证了区间的顺序，否则因为一交换x和y它顺序就不大一样了所以会更麻烦。。就要分上行下行路径之类的讨论一下了。。。 注意提取链的时候Find过程中要考虑前面已经删去的节点对序列中数字的编号的影响，因为删去以后相当于后面的元素整体前移了。 这个题要用long long。

代码

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #define inf 1000000000 using namespace std; int n,m,rt,p[50010],a[100010],next[100010],tot,cnt,top[50010],fa[50010],w[50010],son[50010],size[50010],deep[50010]; struct record{ int bgn,len; void ins(int L,int R){bgn=L;len=R-L+1;} }rec[50010]; struct Node{ Node *ch[2],*fa; int size,dlt; long long sum,data,Max,Min,; bool rev; Node(); bool pl(){return this==fa->ch[1];} void count(){ size=ch[0]->size+ch[1]->size+1; sum=ch[0]->sum+ch[1]->sum+data; Max=max(data,max(ch[1]->Max,ch[0]->Max)); Min=min(data,min(ch[1]->Min,ch[0]->Min)); } void Rever(); void Add(long long v); void push(); }*null,*Root,*root; Node::Node(){ ch[1]=ch[0]=fa=null; size=sum=Max=rev=data=dlt=0; Min=inf; } void Node::Rever(){swap(ch[1],ch[0]);rev^=1;} void Node::Add(long long v){sum+=v*size;data+=v;Max+=v;Min+=v;dlt+=v;} void Node::push(){ if (rev==true){ if (ch[0]!=null) ch[0]->Rever(); if (ch[1]!=null) ch[1]->Rever(); rev=false; } if (dlt!=0){ if (ch[0]!=null) ch[0]->Add(dlt); if (ch[1]!=null) ch[1]->Add(dlt); dlt=0; } } void Rotate(Node* &Rt,Node *k){//注意过程里会修改Rt，所以要传变参 Node *r=k->fa; if (k==null||r==null) return; int x=k->pl()^1; r->push();k->push(); r->ch[x^1]=k->ch[x]; if (k->ch[x]!=null) r->ch[x^1]->fa=r; if (r->fa!=null) r->fa->ch[r->pl()]=k; else Rt=k; k->fa=r->fa; r->fa=k; k->ch[x]=r; r->count();k->count(); } void Splay(Node* &Rt,Node *r,Node *tar){ for (;r->fa!=tar;Rotate(Rt,r)) if (r->fa->fa!=tar) Rotate(Rt,r->pl()==r->fa->pl()?r->fa:r); } void Find(Node* &Rt,int k,Node *tar){ Node *r=Rt; r->push(); while (k!=r->ch[0]->size+1){ if (k<r->ch[0]->size+1) r=r->ch[0]; else{ k=k-r->ch[0]->size-1; r=r->ch[1]; } r->push(); } Splay(Rt,r,tar); } void add(int x,int y){ tot++;a[tot]=y;next[tot]=p[x];p[x]=tot; } void dfs(int u){ deep[u]=deep[fa[u]]+1; size[u]=1;son[u]=0; for (int i=p[u];i!=0;i=next[i]) if (a[i]!=fa[u]){ fa[a[i]]=u; dfs(a[i]); size[u]+=size[a[i]]; if (size[a[i]]>size[son[u]]) son[u]=a[i]; } } void dfs_again(int u,int tp){ top[u]=tp;w[u]=++cnt; if (son[u]!=0) dfs_again(son[u],tp); for (int i=p[u];i!=0;i=next[i]) if (a[i]!=fa[u]&&a[i]!=son[u]) dfs_again(a[i],a[i]); } Node* build(int l,int r){ if (l>r) return null; Node *k=new Node(); int mid=(l+r)>>1; k->size=1; k->ch[0]=build(l,mid-1); k->ch[1]=build(mid+1,r); if (k->ch[0]!=null) k->ch[0]->fa=k; if (k->ch[1]!=null) k->ch[1]->fa=k; k->count(); return k; } void Addnum(int L,int R,int val){ Find(Root,L,null);Find(Root,R+2,Root); Root->ch[1]->ch[0]->Add(val); Root->ch[1]->count(); Root->count(); } void Increase(int x,int y,int val){ while (top[x]!=top[y]){ if (deep[top[x]]<deep[top[y]]) swap(x,y); Addnum(w[top[x]],w[x],val); x=fa[top[x]]; } if (deep[x]>deep[y]) swap(x,y); Addnum(w[x],w[y],val); } long long Get(long long &ans,int L,int R,int opt){ Find(Root,L,null);Find(Root,R+2,Root); Node *k=Root->ch[1]->ch[0]; if (opt==1) ans+=k->sum; if (opt==2) ans=max(ans,k->Max); if (opt==3) ans=min(ans,k->Min); } long long Getinfo(int x,int y,int opt){ long long ans=(opt==3)?inf:0; while (top[x]!=top[y]){ if (deep[top[x]]<deep[top[y]]) swap(x,y); Get(ans,w[top[x]],w[x],opt); x=fa[top[x]]; } if (deep[x]>deep[y]) swap(x,y); Get(ans,w[x],w[y],opt); return ans; } void Reverse(int tot){ Node *k; int newsz=0; for (int i=tot;i>=1;i--){ int L,R; L=rec[i].bgn;R=rec[i].bgn+rec[i].len-1; L-=newsz,R-=newsz;//整体前移 Find(Root,L,null);Find(Root,R+2,Root); k=Root->ch[1]->ch[0]; Root->ch[1]->ch[0]=null; Root->ch[1]->count();Root->count(); Find(root,newsz+1,null);Find(root,newsz+2,root); root->ch[1]->ch[0]=k; k->fa=root->ch[1];//更改节点的父亲不然Rotate的时候会出错 root->ch[1]->count();root->count(); newsz+=k->size; } root->Rever(); for (int i=tot;i>=1;i--){ int L=rec[i].bgn,R; Find(Root,L,null);Find(Root,L+1,Root); L=1;R=rec[i].len;//每次找出与当前长度相等的一段 Find(root,L,null);Find(root,R+2,root); k=root->ch[1]->ch[0]; root->ch[1]->ch[0]=null; root->ch[1]->count();root->count(); Root->ch[1]->ch[0]=k; k->fa=Root->ch[1]; Root->ch[1]->count();Root->count(); } } void Invert(int x,int y){ int cnt=0; while (top[x]!=top[y]){ if (deep[top[x]]<deep[top[y]]) swap(x,y); rec[++cnt].ins(w[top[x]],w[x]); x=fa[top[x]]; } if (deep[x]>deep[y]) swap(x,y); rec[++cnt].ins(w[x],w[y]); Reverse(cnt); } int main() { null=new Node;*null=Node(); scanf("%d%d%d",&n,&m,&rt); for (int i=1;i<n;i++){ int x,y;scanf("%d%d",&x,&y); add(x,y);add(y,x); } dfs(rt);dfs_again(rt,rt); Root=build(0,n+1); root=build(0,1); for (int i=1;i<=m;i++){ char opt[10]; int x,y,val; scanf("%s",opt); scanf("%d%d",&x,&y); if (opt[0]=='I'&&opt[2]=='c'){ scanf("%d",&val);Increase(x,y,val); } if (opt[0]=='S') printf("%I64d\n",Getinfo(x,y,1)); if (opt[0]=='M'&&opt[1]=='a') printf("%d\n",Getinfo(x,y,2)); if (opt[0]=='M'&&opt[1]=='i') printf("%d\n",Getinfo(x,y,3)); if (opt[0]=='I'&&opt[2]=='v') Invert(x,y); } return 0; }