比赛场次 626
比赛名称 并查集专题
比赛状态 已结束比赛成绩
开始时间 2024-09-05 19:00:00
结束时间 2024-09-05 19:05:00
开放分组 全部用户
注释介绍 亲戚:模板题
食物链,银河英雄传说:带权并查集
oiwiki并查集应用:https://oi-wiki.org/topic/dsu-app/
动物园:A
树:D
呜呜呜 :E
Disruption:F
题目名称 永无乡
输入输出 bzoj_2733.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分

永无乡

★★★☆   输入文件:bzoj_2733.in   输出文件:bzoj_2733.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

永无乡包含 $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$ 的正整数,字母与数字以及两个数字之间用空格隔开。

【输出格式】

对于每个 $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

【提示】

对于 20% 的数据 $n\le 1000$,$q\le 1000$。

对于 100% 的数据 $n\le 100000$,$m\le n$,$q\le 300000$。