首页 > 代码库 > 【BZOJ3510】首都 LCT维护子树信息+启发式合并
【BZOJ3510】首都 LCT维护子树信息+启发式合并
【BZOJ3510】首都
Description
在X星球上有N个国家，每个国家占据着X星球的一座城市。由于国家之间是敌对关系，所以不同国家的两个城市是不会有公路相连的。
X星球上战乱频发，如果A国打败了B国，那么B国将永远从这个星球消失，而B国的国土也将归A国管辖。A国国王为了加强统治，会在A国和B国之间修建一条公路，即选择原A国的某个城市和B国某个城市，修建一条连接这两座城市的公路。
同样为了便于统治自己的国家，国家的首都会选在某个使得其他城市到它距离之和最小的城市，这里的距离是指需要经过公路的条数，如果有多个这样的城市，编号最小的将成为首都。
现在告诉你发生在X星球的战事，需要你处理一些关于国家首都的信息，具体地，有如下3种信息需要处理：
1、A x y：表示某两个国家发生战乱，战胜国选择了x城市和y城市，在它们之间修建公路（保证其中城市一个在战胜国另一个在战败国）。
2、Q x：询问当前编号为x的城市所在国家的首都。
3、Xor：询问当前所有国家首都编号的异或和。
Input
第一行是整数N，M，表示城市数和需要处理的信息数。
接下来每行是一个信息，格式如题目描述（A、Q、Xor中的某一种）。
Output
输出包含若干行，为处理Q和Xor信息的结果。
Sample Input
Xor
Q 1
A 10 1
A 1 4
Q 4
Q 10
A 7 6
Xor
Q 7
Xor
Sample Output
1
1
1
2
6
2
HINT
对于100%的数据，2<=N<=100000，1<=M<=200000。
题解：考虑每次将小的树合并到大的树上，这样每次大树的重心移动距离不会超过（小树的大小+1），那么我们只需要知道重心移动到了哪里。
可以确定的是，一棵树最多只有相邻的两个重心，所以我们如果想将b接到a的子树上，那么新的重心一定在（原重心-b）的这条链上，并且距离不超过（b树的大小+1）,所以我们将对b进行access操作，在对原重心进行splay操作，这样的话这条链上的所有点就都在这棵splay里了，我们可以对splay进行中序遍历，就能将这些点都按顺序拿出来。
那么我们如何确定该以哪个为根呢？我们考虑根从一个点跳到它的儿子时是否会令答案更优，这就需要我们求出每个点的子树大小。我们只需要将当前点splay一下，然后它在LCT中的子树大小就是它在原树中的子树大小了（用LCT维护子树信息的方法不在赘述）。
本题的细节就在于要时刻注意splay,access和计算的顺序，即有时候的子树大小并不是真的大小，还需要进行一系列的操作（或者在进行某些操作后，子树大小就变了），还有别忘了中序遍历的时候需要pushdown。
#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int maxn=100010;int n,m,tot,nr,sum;struct splay{ int sx,sl,ch[2],fa,rev;}s[maxn];int p[maxn];char str[10];bool isr(int x) {return s[s[x].fa].ch[0]!=x&&s[s[x].fa].ch[1]!=x;}void pushup(int x) {s[x].sl=s[x].sx+s[s[x].ch[0]].sl+s[s[x].ch[1]].sl+1;}void pushdown(int x){ if(s[x].rev) { swap(s[x].ch[0],s[x].ch[1]),s[x].rev=0; if(s[x].ch[0]) s[s[x].ch[0]].rev^=1; if(s[x].ch[1]) s[s[x].ch[1]].rev^=1; }}void updata(int x){ if(!isr(x)) updata(s[x].fa); pushdown(x);}void rotate(int x){ int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]); if(!isr(y)) s[z].ch[y==s[z].ch[1]]=x; s[y].fa=x,s[x].fa=z,s[y].ch[d]=s[x].ch[d^1]; if(s[x].ch[d^1]) s[s[x].ch[d^1]].fa=y; s[x].ch[d^1]=y; pushup(y),pushup(x);}void splay(int x){ updata(x); while(!isr(x)) { int y=s[x].fa,z=s[y].fa; if(!isr(y)) { if((y==s[z].ch[0])^(x==s[y].ch[0])) rotate(x); else rotate(y); } rotate(x); }}void access(int x){ for(int y=0;x;splay(x),s[x].sx-=s[y].sl-s[s[x].ch[1]].sl,s[x].ch[1]=y,pushup(x),y=x,x=s[x].fa);}void maker(int x){ access(x),splay(x),s[x].rev^=1;}void link(int x,int y){ maker(x),access(y),splay(y),s[y].sx+=s[x].sl,s[x].fa=y,pushup(y);}int findr(int x){ access(x),splay(x),pushdown(x); while(s[x].ch[0]) x=s[x].ch[0],pushdown(x); return x;}void query(int x,int y){ if(!x) return ; pushdown(x); query(s[x].ch[0],y); if(p[0]>=y) return ; p[++p[0]]=x; if(p[0]>=y) return ; query(s[x].ch[1],y);}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("bz3510.in","r",stdin); n=rd(),m=rd(); int i,j,a,b,c,d,e,sc,sd; for(i=1;i<=n;i++) s[i].sl=1,sum^=i; for(i=1;i<=m;i++) { scanf("%s",str); if(str[0]==‘X‘) printf("%d\n",sum); if(str[0]==‘Q‘) printf("%d\n",findr(rd())); if(str[0]==‘A‘) { a=rd(),b=rd(),c=findr(a),splay(c),d=findr(b),splay(d),sc=s[c].sl,sd=s[d].sl; if(sc<sd||(sc==sd&&c>d)) swap(c,d),swap(a,b),swap(sc,sd); link(b,a),access(b),splay(c),p[0]=0,tot=sc+sd,query(c,sd+1),nr=c; for(j=1;j<=p[0];j++) { splay(p[j]); e=s[p[j]].sx+1+(s[p[j]].ch[1]>0?s[s[p[j]].ch[1]].sl:0); if(tot-e<e||(tot-e==e&&p[j]<=nr)) nr=p[j]; else break; } maker(nr),sum^=nr,sum^=c,sum^=d; } } return 0;}【BZOJ3510】首都 LCT维护子树信息+启发式合并