P3224 [HNOI2012]永无乡[splay]

题目描述

永无乡包含 n 座岛,编号从 1 到 n,每座岛都有自己的独一无二的重要度,按照重要度可 以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座(含 0 座)桥可以到达岛 b,则称岛 a 和岛 b 是连 通的。

现在有两种操作:

B x y 表示在岛 x 与岛 y 之间修建一座新桥。

Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛,即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座,请你输出那个岛的编号。

输入输出格式

输入格式:

输入文件第一行是用空格隔开的两个正整数 $n$ 和 $m$,分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 $n$ 个数,依次描述从岛 $1$ 到岛 $n$ 的重要度排名。随后的 $m$ 行每行是用空格隔开的两个正整数 $a_i$ 和 $b_i$,表示一开始就存 在一座连接岛 $a_i$ 和岛 $b_i$ 的桥。后面剩下的部分描述操作,该部分的第一行是一个正整数 $q$, 表示一共有 $q$ 个操作,接下来的 $q$ 行依次描述每个操作,操作的格式如上所述,以大写字母 Q 或B 开始,后面跟两个不超过 $n$ 的正整数,字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 $n\le1000$,$q\le1000$ 对于 100%的数据 $n\le 100000$,$m\le n$,$q\le 300000$

输出格式:

对于每个 Q x k 操作都要依次输出一行,其中包含一个整数,表 示所询问岛屿的编号。如果该岛屿不存在,则输出 $-1$。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
10
11
5  1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3

输出样例#1:

1
2
3
4
5
-1
2
5
1
2

题解

接近于模板题。

合并操作就把点拆了,一个一个合并,

然后是把小的合到大的中,

这样每个点合并的次数的和不会超过$O(n \ln n)$。

然后我手滑最开始没有把size赋位1。

这个代码卡了点常,所以长得丑。

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
char s;
int k=0;
while((s=getchar())!='-'&&!(isdigit(s)));
while(isdigit(s))
{
k=k*10+(s^'0');
s=getchar();
}
return k;
}
inline void write(int x)
{
static char cnt,num[15];cnt=0;
if (!x) {putchar('0'); return;}
for (;x;x/=10) num[++cnt]=x%10;
for (;cnt;putchar(num[cnt--]+48));
}
const int maxn=1e5+5;
int n,m,X,Y,tot,root[maxn],Fa[maxn];
int fa[maxn],ch[maxn][2],num[maxn],id[maxn];//num,权值
int sz[maxn];

#define rs(x) ch[fa[(x)]][1]==(x)

int gf(int x)
{
return Fa[x]==x?x:Fa[x]=gf(Fa[x]);
}
#define maintain(x) sz[(x)]=sz[ch[(x)][0]]+sz[ch[(x)][1]]+1
inline void rotate(int x)
{
int k=rs(x),y=fa[x],ft=fa[y];
ch[y][k]=ch[x][k^1];
fa[ch[y][k]]=y;

ch[ft][rs(y)]=x;
fa[x]=ft;

ch[x][k^1]=y;
fa[y]=x;

maintain(y);maintain(x);
if (fa[x]==0) root[gf(x)]=x;
}
inline void splay(int x)
{
while (fa[x]!=0)
{
if (fa[fa[x]]!=0) (rs(fa[x])^rs(x))?rotate(x):rotate(fa[x]);
rotate(x);
}
root[gf(x)]=x;
}
inline void insert(int x,int y)//点x插到树y
{
int now=root[gf(y)],ft;
while (now!=0)
{
ft=now;
sz[now]++;
now=num[x]<num[now]?ch[now][0]:ch[now][1];
}
fa[x]=ft;
sz[x]=1;
ch[ft][num[ft]<num[x]]=x;
splay(x);
}
void dfs(int x,int y)//树x合到树y
{
if (ch[x][0]!=0) dfs(ch[x][0],y);
if (ch[x][1]!=0) dfs(ch[x][1],y);
ch[x][0]=0;ch[x][1]=0;
insert(x,y);
}
inline void merge(int x,int y)
{
if (gf(x)==gf(y)) return;
x=gf(x);y=gf(y);
if (sz[root[y]]<sz[root[x]]) swap(x,y);
Fa[x]=gf(y);
dfs(root[x],y);
}
int Kth(int x,int y)//树x中第y小
{
int now=x;
sz[0]=0;
while (now!=0)
{
if (sz[ch[now][0]]>=y)
{
now=ch[now][0];
} else
if (sz[ch[now][0]]==y-1) return now; else
{
y-=sz[ch[now][0]]+1;
now=ch[now][1];
}
}
}
char Ch[5];
int main()
{
n=read();m=read();
for (int i=1;i<=n;i++)
{
num[i]=read();id[i]=i;root[i]=i;Fa[i]=i;sz[i]=1;
}
for (int i=1;i<=m;i++)
{
X=read();Y=read();
merge(X,Y);
}
m=read();
while (m--)
{
scanf("%s",Ch+1);
X=read();Y=read();
if (Ch[1]=='Q')
{
X=root[gf(X)];
if (sz[X]<Y) printf("-1\n"); else
write(Kth(X,Y)),putchar('\n');
} else merge(X,Y);
}
return 0;
}