Description
永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。
Input
输入文件第一行是用空格隔开的两个正整数 n 和 m，分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q， 表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 n≤1000,q≤1000 对于 100%的数据 n≤100000,m≤n，q≤300000
Output
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表 示所询问岛屿的编号。如果该岛屿不存在，则输出-1。
Sample Input
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
Sample Output
-1 2 5 1 2
用平衡树维护一下，把小平衡树拆到大平衡树里
没有旋转居然过了
#include <cstdio>
#include <cstring>
#include <
string>
using namespace std;
int n,k;
const int maxn=
101000;
int f[maxn],key[maxn],sum[maxn],fa[maxn];
int size[maxn],a[maxn],son[maxn][
2];
int up(
int x)
{ sum[x]=sum[son[x][
1]]+sum[son[x][
0]]+
1;
}
int rotate(
int x)
{ int y=
f[x];
int w=(son[y][
0]==
x);
son[y][!w]=
son[x][w];
if (son[x][w]) f[son[x][w]]=
y;
if (f[y])
{ int z=f[y]; son[z][son[z][
1]==y]=
x;
}
f[x]=f[y]; son[x][w]=y; f[y]=
x;
up(y); up(x);}
int m;
int root(
int x)
{ while (f[x]) x=
f[x];
return x; }
int find(
int x)
{ if (fa[x]==x)
return x;
fa[x]=find(fa[x]);
return fa[x];
}
int ins(
int x,
int y)
{ if (key[x]<
key[y])
{ if (!son[y][
0]) {son[y][
0]=x;f[x]=
y;}
else ins(x,son[y][
0]);
}
else
{ if (!son[y][
1]) {son[y][
1]=x;f[x]=
y;}
else
ins(x,son[y][1]);
}
up(y);
}
int clear(
int x)
{ f[x]=son[x][
0]=son[x][
1]=
0; sum[x]=
1;
}
int dfs(
int x,
int f)
{ if (!x)
return 0;
dfs(son[x][0],f);
dfs(son[x][1],f);
clear(x); ins(x,root(f));
}
int unio(
int x,
int y)
{ int w1=
find(x);
int w2=
find(y);
if (w1==w2)
return 0;
if (size[w1]<=
w2)
{dfs(root(w1),w2);f[w1]=w2;size[w2]+=
size[w1];}
else {dfs(root(w2),w1); f[w2]=w1; size[w1]+=
size[w2];}
}
int ask(
int f,
int k)
{ if (!f)
return -
1;
if (sum[son[f][
0]]+
1==k)
return f;
if (sum[son[f][
0]]+
1<
k)
return ask(son[f][
1],k-sum[son[f][
0]]-
1);
else return ask(son[f][
0],k);
}
int main()
{ scanf("%d%d",&n,&k);
int x,y;
for (
int i=
1;i<=n;i++
)
scanf("%d",&key[i]),sum[i]=
1,f[i]=
0,fa[i]=i,size[i]=
1;
for (
int i=
1;i<=k;i++
)
scanf("%d%d",&x,&
y),unio(x,y);
scanf("%d",&m);
char s[
10];
while (m--
)
{ scanf("%s",&s); scanf(
"%d%d",&x,&
y);
if (s[
0]==
'B') unio(x,y);
if (s[
0]==
'Q')
{ int tmp=
root(x);
printf("%d\n",ask(tmp,y));}
}
return 0;
}
转载于:https://www.cnblogs.com/williamchenwl/p/3638614.html
相关资源：JAVA上百实例源码以及开源项目
