【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

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

轉載于:https://www.cnblogs.com/CQzhangyu/p/7061265.html