【Bzoj2733】【Luogu3224】永无乡

来源和评测点

HNOI2012
Bzoj2733
Luogu3224

题目

【题目大意】
永无乡包含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 行每行是用空格隔开的两个正整数 ai 和 bi,
表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。
后面剩下的部分描述操作,该部分的第一行是一个正整数 q,
表示一共有 q 个操作,接下来的 q 行依次描述每个操作,
操作的格式如上所述,以大写字母 Q 或B 开始,
后面跟两个不超过 n 的正整数,字母与数字以及两个数字之间用空格隔开。

对于 20%的数据 n≤1000,q≤1000
对于 100%的数据 n≤100000,m≤n,q≤300000
【输出格式】
对于每个 Q x k 操作都要依次输出一行,
其中包含一个整数,表示所询问岛屿的编号。
如果该岛屿不存在,则输出-1。
【输入样例】
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
2
5
1
2

刷题记录

1h
1AC

分析

并查集维护连通性
权值线段树维护数量来找大小
注意类似主席树的合并
跑得还是很快的,至于别的解法,不管了
就算被卡,在考场上也是很优秀的算法,因为代码复杂度很低

代码

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
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
//*******************全局常量*******************
const int MAXN=110000;
//*******************全局定义*******************
struct nod
{
int lc,rc;
int c;
}p[21*MAXN];
int rt[MAXN];
//*******************线段树*******************
int ln=0;
void change(int &x,int l,int r,int pos)
{
if(x==0)
{
x=++ln;
p[x].c=0;
p[x].lc=p[x].rc=0;
}
p[x].c++;
if(l==r) return;
int mid=(l+r)/2;
if(pos<=mid) change(p[x].lc,l,mid,pos);
else change(p[x].rc,mid+1,r,pos);
}
void merg(int x,int &y)
{
if(x==0) return;
if(y==0) {y=x;return;}
p[y].c+=p[x].c;
merg(p[x].lc,p[y].lc);
merg(p[x].rc,p[y].rc);
}
int find(int x,int l,int r,int k)
{
if(k==0 or k>p[x].c) return 0;
if(l==r) return l;
int mid=(l+r)/2,lc=p[x].lc;
if(k<=p[lc].c) return find(p[x].lc,l,mid,k);
return find(p[x].rc,mid+1,r,k-p[lc].c);
}
//*******************并查集*******************
int fa[MAXN];
int findfa(int x)
{
if(fa[x]==x) return x;
return fa[x]=findfa(fa[x]);
}
void join(int x,int y)
{
int fx=findfa(x),fy=findfa(y);
if(fx!=fy)
{
fa[fx]=fy;
merg(rt[fx],rt[fy]);
}
}
//*******************主函数*******************
int id[MAXN],id2[MAXN];
int main()
{
memset(rt,0,sizeof(rt));
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&id[i]);
fa[i]=i;id2[id[i]]=i;
change(rt[i],1,n,id[i]);
}
id2[0]=-1;
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
join(a,b);
}
int q;scanf("%d",&q);
while(q--)
{
char s[20];int a,b;
scanf("%s%d%d",s,&a,&b);
if(s[0]=='B') join(a,b);
else printf("%d\n",id2[ find(rt[ findfa(a) ],1,n,b) ]);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/6053.html
转载请注明出处,谢谢!