「Luogu 4299」首都

发表于 | | 阅读次数:
字数统计: 1.4k 字

Description

题目链接：Luogu 4299

在 X 星球上有 $n$ 个国家，每个国家占据着 X 星球的一座城市。由于国家之间是敌对关系，所以不同国家的两个城市是不会有公路相连的。

X 星球上战乱频发，如果 A 国打败了 B 国，那么 B 国将永远从这个星球消失，而 B 国的国土也将归 A 国管辖。A 国国王为了加强统治，会在 A 国和 B 国之间修建一条公路，即选择原 A 国的某个城市和 B 国某个城市，修建一条连接这两座城市的公路。

同样为了便于统治自己的国家，国家的首都会选在某个使得其他城市到它距离之和最小的城市，这里的距离是指需要经过公路的条数，如果有多个这样的城市，编号最小的将成为首都。

现在告诉你发生在 X 星球的战事，需要你处理 $m$ 条关于国家首都的信息，具体地，有如下 $3$ 种信息需要处理：

  • A x y：表示某两个国家发生战乱，战胜国选择了 $x$ 城市和 $y$ 城市，在它们之间修建公路（保证其中城市一个在战胜国另一个在战败国）。
  • Q x：询问当前编号为 $x$ 的城市所在国家的首都。
  • Xor：询问当前所有国家首都编号的异或和。

数据范围：$2\le n\le 10^5$，$1\le m\le 2\times 10^5$

Solution

用 $\text{LCT}​$ 来维护子树信息。这里有一个重心的性质：两棵树合并后的重心一定在原来两个重心的链上。

于是我们考虑对这条路径二分。记 $lsum$ 表示搜索区间左端点以左的子树大小总和，类似的 $rsum$ 表示右端点以右的。当前搜索区间就是子树 $x$，显然 $x$ 作为根把搜索区间分成了左右两块（在 $\text{Splay}$ 中对应 $x$ 的左子树和右子树）。

对于重心的判定：如果 $sz_{x\ \text{的左子树}}+lsum​$ 和 $sz_{x\ \text{的右子树}}+rsum​$ 都不超过整棵树的大小的一半，那么这个点 $x​$ 就是重心。对于总大小是奇数的，重心有且只有 $1​$ 个；否则为了得到编号最小的重心，必须继续找下去。

接下来我们要往儿子里寻找答案，我们贪心地选择 $x$ 的儿子节点。如果 $sz_{x\ \text{的左子树}}+lsum<sz_{x\ \text{的右子树}}+rsum$，那么我们进入右儿子；并把 $lsum$ 加上左儿子的总大小和 $x$ 的虚子树大小。反之同理。

由于 $\text{Splay}$ 有很优秀的期望 $O(\log n)$ 的深度，因此每次找重心的复杂度为 $O(\log n)$！

最后提一些细节：

  1. 在 $\text{LCT}$ 维护子树信息时，$\text{link}$ 操作时会有影响。$y$ 会多出一个轻儿子 $x$，那么 $y$ 的所有祖先的信息都要更新。这是一般写法不能胜任的。我们必须把 $y$ 转到根节点才不会影响正确性。代码中 split(x,y) 是 makeroot(x),access(y),splay(y) 的偷懒写法。
  2. 使用 findroot 找重心太慢了。我们直接用并查集来维护每个点所在树的重心。
  3. 在二分找重心的过程中，提取子树信息前一定要记得下传标记！

时间复杂度：$O(m\log n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
#include <cstdio>
#include <algorithm>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]

const int N=1e5+5;
int n,m,fa[N],ch[N][2],sz[N],si[N],st[N],f[N];
bool rev[N];

bool get(int x) {
    return rs(fa[x])==x;
}
bool isroot(int x) {
    return ls(fa[x])!=x&&rs(fa[x])!=x;
}
void reverse(int x) {
    rev[x]^=1,std::swap(ls(x),rs(x));
}
void pushup(int x) {
    sz[x]=sz[ls(x)]+sz[rs(x)]+si[x]+1;
}
void pushdown(int x) {
    if(rev[x]) reverse(ls(x)),reverse(rs(x)),rev[x]=0;
}
void rotate(int x) {
    int y=fa[x],z=fa[y],k=get(x);
    !isroot(y)&&(ch[z][get(y)]=x),fa[x]=z;
    ch[y][k]=ch[x][!k],fa[ch[x][!k]]=y;
    ch[x][!k]=y,fa[y]=x;
    pushup(y),pushup(x);
}
void splay(int x) {
    int u=x,tp=0;
    st[++tp]=u;
    while(!isroot(u)) st[++tp]=u=fa[u];
    while(tp) pushdown(st[tp--]);
    while(!isroot(x)) {
        int y=fa[x];
        if(!isroot(y)) rotate(get(x)==get(y)?y:x);
        rotate(x);
    }
}
void access(int x) {
    for(int y=0;x;x=fa[y=x]) {
        splay(x);
        si[x]+=sz[rs(x)];
        si[x]-=sz[rs(x)=y];
        pushup(x);
    }
}
void makeroot(int x) {
    access(x),splay(x),reverse(x);
}
void split(int x,int y) {
    makeroot(x),access(y),splay(y);
}
void link(int x,int y) {
    split(x,y),si[fa[x]=y]+=sz[x],pushup(y);
}
int solve(int x) {
    int sum=sz[x]>>1,o=sz[x]&1,ans=1<<30,lsum=0,rsum=0;
    while(x) {
        pushdown(x);
        int l=ls(x),r=rs(x),nl=sz[l]+lsum,nr=sz[r]+rsum;
        if(nl<=sum&&nr<=sum) {
            if(o) {ans=x;break;}
            if(x<ans) ans=x;
        }
        if(nl<nr) lsum+=sz[l]+si[x]+1,x=r;
        else rsum+=sz[r]+si[x]+1,x=l;
    }
    splay(ans);
    return ans;
}
int find(int x) {
    return f[x]==x?x:f[x]=find(f[x]);
}
int main() {
    scanf("%d%d",&n,&m);
    int Xor=0;
    for(int i=1;i<=n;++i) f[i]=i,Xor^=i;
    while(m--) {
        char s[5];
        scanf("%s",s);
        if(s[0]=='X') {
            printf("%d\n",Xor);
        } else if(s[0]=='Q') {
            int x;
            scanf("%d",&x);
            printf("%d\n",find(x));
        } else {
            int x,y;
            scanf("%d%d",&x,&y);
            link(x,y);
            split(x=find(x),y=find(y));
            int z=solve(y);
            f[x]=f[y]=f[z]=z;
            Xor^=x^y^z;
        }
    }
    return 0;
}
0%