【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

10 10
Xor
Q 1
A 10 1
A 1 4
Q 4
Q 10
A 7 6
Xor
Q 7
Xor

Sample Output

11
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;
}

最新文章

  1. [LeetCode] Pascal&#39;s Triangle II 杨辉三角之二
  2. linux升级openssl
  3. RichTextBox着色与着色不闪
  4. Java基础-CGLIB动态代理
  5. linux web服务器静态资源的处理 unison+inotify双向同步
  6. [原]sdut2605 A^X mod P 山东省第四届ACM省赛(打表,快速幂模思想,哈希)
  7. Win7 不能安装 msi 解决办法
  8. POJ2222+暴力搜索
  9. C/C++中memset函数
  10. 解决ubuntu合盖后无法唤醒
  11. CreateFont具体解释
  12. 191. Number of 1 Bits Leetcode Python
  13. 微信小程序首页总结
  14. 在jquery中each循环中,要用return false代替break,return true代替continue。
  15. PhpStrom如何安装主题?(总结三种不同格式安装方法)
  16. Spring rabbitMq 中 correlationId或CorrelationIdString 消费者获取为null的问题
  17. (24/24) webpack小案例--自己动手用webpack构建一个React的开发环境
  18. session图片验证码,页面和请求是两个地址。android手机好用,iphone 失效。
  19. nio 阻塞 非阻塞 同步 异步
  20. Java执行JavaScript代码

热门文章

  1. DotNetBrowser入门教程(更新完善中)
  2. json格式在线解析
  3. [转载]使用java.lang.Process类的简单例子
  4. NYOJ 49 开心的小明(01背包问题)
  5. SOYO的主板如何进入BIOS系统
  6. configure.ac:8: error: Autoconf version 2.64 or higher is required
  7. debounce 防抖动函数
  8. C++_友元函数(转)
  9. windows快捷键之打开网络连接
  10. ASP.NET CORE RAZOR :初始化数据库