rockdu
题目描述
永无乡包含 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。
输入输出样例
输入样例#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： 复制这是裸的线段树合并啊，不知道自己以前为什么会去想平衡树，(/≧▽≦)/。
-1 2 5 1 2
这是裸的线段树合并啊，不知道自己以前为什么会去想平衡树，(/≧▽≦)/。
建N个权值线段树随便并并就AC了，调试都不用，做题体验极佳。
#include<cstdio>
#include<cctype>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, a, b, f;
char s;
inline char gc(){
static char buf[4000000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 4000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int & x) {
x = 0, f = 0;static char c = gc();
while(!isdigit(c)) {
if(c == '-') f = 1;
c = gc();
}
while(isdigit(c)) x = x * 10 + c - '0', c = gc();
if(f) x = -x;
}
inline void rc(char & x) {
x = gc();
while(x != 'Q' && x != 'B') x = gc();
}
namespace SGT {
const int L = 0, R = 1;
int root[maxn], cnt;
struct node {
int sum, chl, chr, id;
}tree[maxn * 20];
void push_up(int rt) {
tree[rt].sum = tree[tree[rt].chl].sum + tree[tree[rt].chr].sum;
}
int merge(int x, int y) {
if(!x || !y) return x + y;
tree[x].sum += tree[y].sum;
tree[x].chl = merge(tree[x].chl, tree[y].chl);
tree[x].chr = merge(tree[x].chr, tree[y].chr);
return push_up(x), x;
}
void build(int tl, int tr, int pos, int id, int & rt) {
rt = ++cnt;
if(tl == tr) {tree[rt].sum = 1, tree[rt].id = id; return;}
int mid = tl + tr >> 1;
if(pos <= mid) build(tl, mid, pos, id, tree[rt].chl);
else build(mid + 1, tr, pos, id, tree[rt].chr);
push_up(rt);
}
int query(int tl, int tr, int k, int rt) {
if(tl == tr) return tree[rt].id;
int mid = tl + tr >> 1;
if(tree[tree[rt].chl].sum >= k) return query(tl, mid, k, tree[rt].chl);
else return query(mid + 1, tr, k - tree[tree[rt].chl].sum, tree[rt].chr);
}
}
namespace DSU {
int fa[maxn];
void init(int x) {for(register int i = 1; i <= x; ++i) fa[i] = i;}
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void combine(int a, int b) {fa[find(b)] = find(a);}
}
int main() {
using namespace SGT;
read(n), read(m), DSU::init(n), tree[0].id = -1;
for(register int i = 1; i <= n; ++i)
read(a), SGT::build(1, n, a, i, SGT::root[i]);
for(register int i = 1; i <= m; ++i) {
read(a), read(b);
if((a = DSU::find(a)) == (b = DSU::find(b))) continue;
SGT::merge(SGT::root[a], SGT::root[b]);
DSU::combine(a, b);
}
read(m);
while(m--) {
rc(s), read(a), read(b);
if(s == 'Q') printf("%d\n", SGT::query(1, n, b, SGT::root[DSU::find(a)]));
if(s == 'B') {
a = DSU::find(a), b = DSU::find(b);
SGT::root[b] = SGT::merge(SGT::root[a], SGT::root[b]);
DSU::combine(a, b);
}
}
return 0;
}
没有帐号? 立即注册