2733: [HNOI2012] 永无乡
永 无乡包含 n 座岛,编号从 1 到 n,每座岛都有自己的独一无二的重要度,按照重要度可 以将这 n 座岛排名,名次用 1 到 n 来表示.某些岛之间由巨大的桥连接,通过桥可以从一个岛 到达另一个岛.如果从岛 a 出发经过若干座(含 0 座)桥可以到达岛 b,则称岛 a 和岛 b 是连 通的.现在有两种操作:B x y 表示在岛 x 与岛 y 之间修建一座新桥.Q x k 表示询问当前与岛 x 连通的所有岛中第 k 重要的是哪座岛,即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座,请你输出那个岛的编号.
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 4426 Solved: 2363
[ Submit ][ Status ][ Discuss ]
Description
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.
[题解] 不难看出启发式合并.我写完之后突然发现....尼玛我 TM 怎么全程没有用过 splay? 丁队早期的板子有点不靠谱啊...我查了查才知道...insert 后需要 splay(本题不行,除非执行删除节点操作)getk 需要 splay... 反正啥啥都得 splay 一下..还好现在发现了,不然命丧 IOI2019(???)
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
HINT
Source
/**************************************************************
Problem: 2733
User: 33511595
Language: C++
Result: Accepted
Time:3168 ms
Memory:4808 kb
****************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
template <class T>
inline void swap(T& a, T& b)
{
T tmp = a;a = b;b = tmp;
}
inline void read(int &x)
{
x = 0;char ch = getchar(), c = ch;
while(ch < '0' || ch > '9') c = ch, ch = getchar();
while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
if(c == '-') x = -x;
}
const int INF = 0x3f3f3f3f;
const int MAXN = 100000 + 10;
int fa[MAXN], ch[MAXN][2], size[MAXN], cnt[MAXN], data[MAXN], node[MAXN], n, nn, root[MAXN], father[MAXN];
int find(int x)
{
return x == father[x] ? x : father[x] = find(father[x]);
}
int son(int x){return x == ch[fa[x]][1];}
void pushup(int x)
{
size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
}
// 编号为 k 的平衡树
void rotate(int x, int k)
{
int y = fa[x], z = fa[y], b = son(x), c = son(y), a = ch[x][!b];
if(z) ch[z][c] = x; else root[k] = x; fa[x] = z;
if(a) fa[a] = y; ch[y][b] = a;
ch[x][!b] = y, fa[y] = x;
pushup(y), pushup(x);
}
// 编号为 k 的平衡树
void splay(int x, int i, int k)
{
while(fa[x] != i)
{
int y = fa[x], z = fa[y];
if(z == i) rotate(x, k);
else
if(son(x) == son(y)) rotate(y, k), rotate(x, k);
else rotate(x, k), rotate(x, k);
}
}
// 编号为 k 的平衡树
int getmn(int rt, int k)
{
int ans = -1;
while(rt)
{
ans = rt;
rt = ch[rt][0];
}
if(ans != -1) splay(ans, 0, k);
return ans;
}
// 编号为 k 的平衡树
int getkth(int rt, int kk, int k)
{
int l = ch[rt][0];
if(size[l] + 1 <= kk && kk <= size[l] + cnt[rt])
{
splay(rt, 0, k);
return rt;
}
else if(size[l] + 1 > kk) return getkth(l, kk, k);
else return getkth(ch[rt][1], kk - size[l] - cnt[rt], k);
}
// 插入节点 zz
void insert(int &rt, int zz)
{
if(rt == 0)
{
rt = zz, size[zz] = 1;
return;
}
if(data[zz] < data[rt]) insert(ch[rt][0], zz), fa[ch[rt][0]] = rt;
else if(data[zz] > data[rt]) insert(ch[rt][1], zz), fa[ch[rt][1]] = rt;
pushup(rt);
}
// 把以 x 节点为根的树插入到以 y 节点为根的树上
void dfs(int x, int y, int k)
{
if(!x) return;
int tmp = y;
insert(tmp, x);
dfs(ch[x][0], y, k);
dfs(ch[x][1], y, k);
}
// 把编号为 y 的岛与编号为 x 的岛连接,y 插入到 x
void lk(int x, int y)
{
int f1 = find(x), f2 = find(y);
if(f1 == f2) return;
if(size[root[f1]] < size[root[f2]]) swap(f1, f2);
dfs(root[f2], root[f1], f1);
father[f2] = f1;
}
// 查询与 x 联通的岛中第 y 重要的岛
void ask(int x, int y)
{
int t = find(x), tmp = root[t];
if(size[tmp] < y) printf("-1\n");
else printf("%d\n", node[getkth(tmp, y, t)]);
}
int m,q,tmp1,tmp2;
char c;
int main()
{
read(n);read(m);
for(int i = 1;i <= n;++ i) read(tmp1), father[i] = i, root[i] = i, data[i] = tmp1, node[i] = i, cnt[i] = 1, ++ nn, size[i] = 1;
for(int i = 1;i <= m;++ i) read(tmp1), read(tmp2), lk(tmp1, tmp2);
read(q);
for(int i = 1;i <= q;++ i)
{
scanf("%s", &c), read(tmp1), read(tmp2);
if(c == 'Q') ask(tmp1, tmp2);
else lk(tmp1, tmp2);
}
return 0;
}
BZOJ2733
来源: http://www.bubuko.com/infodetail-2478919.html