[DS记录]P4299 首都
command_block
·
·
个人记录
题意 : 给出一个森林,支持加边,维护每个连通块的重心。
------------
首先，不难想到一种合并方法 ： 连边后 `dfs` 求出新的重心。
然而，合并的复杂度不是 是 $O(s_1+s_2)$ ，不能用于启发式合并。
考虑使用 `LCT` .
容易想到如下憨逼做法 : 连通块 $A,B$ 合并时，设 $s_1=|A|,s_2=|B|,s_1\leq s_2$，取 $A$ 中的点一个个`Link`，每次检查重心是否需要移动。显然，最多移动一次。
这样的总复杂度是 $O(n \log^2 n)$ 的。
(对 $O(s_2\log n)$ 和 $O(s_1+s_2)$ 取 $\min$ 即可得 $O(n\log n\log_n/\log\log n)$ 的复杂度)
启发式合并揭示了一些性质 : 重心移动的次数是 $O(s_1)$ 的。
容易发现，新的重心一定在两个旧重心之间的路径上.
考虑直接整块 `Link` 之后，提取出新旧重心之间的路径， `Splay` 上二分即可。
复杂度为 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 100500
using namespace std;
int n,m;
struct Node{
int l,r,c,pc,f;bool tr;
inline void rev()
{tr^=1;swap(l,r);}
}a[MaxN];
inline void up(int u)
{a[u].c=a[a[u].l].c+a[a[u].r].c+a[u].pc;}
inline void ladd(int u){
if (a[u].tr){
a[a[u].l].rev();
a[a[u].r].rev();
a[u].tr=0;
}
}
inline bool nrt(int u)
{return a[a[u].f].l==u||a[a[u].f].r==u;}
inline void rot(int u)
{
int fa=a[u].f,gf=a[fa].f;
ladd(fa);ladd(u);
if (a[gf].l==fa)a[gf].l=u;
if (a[gf].r==fa)a[gf].r=u;
a[a[fa].f=u].f=gf;
if (a[fa].l==u){
a[a[fa].l=a[u].r].f=fa;
a[u].r=fa;
}else {
a[a[fa].r=a[u].l].f=fa;
a[u].l=fa;
}up(fa);up(u);
}
void splay(int u)
{
ladd(u);
while(nrt(u)){
int fa=a[u].f,gf=a[fa].f;
if (!((a[fa].l==u)^(a[gf].l==fa))&&nrt(fa))rot(fa);
rot(u);
}
}
void access(int x)
{
for (int y=0;x;x=a[y=x].f){
splay(x);
a[x].pc=a[x].pc+a[a[x].r].c-a[y].c;
a[x].r=y;up(x);
}
}
void makrt(int x)
{access(x);splay(x);a[x].rev();}
int findrt(int x){
access(x);splay(x);
while(a[x].l){ladd(x);x=a[x].l;}
splay(x);return x;
}
void spilt(int x,int y)
{makrt(x);access(y);splay(y);}
void link(int x,int y)
{
spilt(x,y);
a[a[x].f=y].pc+=a[x].c;
up(y);
}
int kth(int u,int k)
{
ladd(u);
if (k&&k<=a[a[u].l].c)return kth(a[u].l,k);
else if (k>a[a[u].l].c+a[u].pc)return kth(a[u].r,k-a[a[u].l].c-a[u].pc);
else return u;
}
int ss;
char op[4];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){a[i].pc=a[i].c=1;ss^=i;}
for (int i=1,u,v;i<=m;i++){
scanf("%s",op);
if (op[0]=='X')printf("%d\n",ss);
else if (op[0]=='Q'){
scanf("%d",&u);
printf("%d\n",findrt(u));
}else {
scanf("%d%d",&u,&v);
int wu=findrt(u),wv=findrt(v),
su=a[wu].c,sv=a[wv].c;
ss^=wu;ss^=wv;
link(u,v);spilt(wu,wv);
if ((su+sv)&1){
int w=kth(wv,(su+sv+1)/2);
splay(w);ss^=w;makrt(w);
}else {
int w1=kth(wv,(su+sv)/2),w2=kth(wv,(su+sv)/2+1),w=min(w1,w2);
splay(w);ss^=w;makrt(w);
}
}
}return 0;
}
```