bzoj2733 [HNOI2012]永无乡
题目描述
永无乡包含 n 座岛，编号从 1 到 n ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛aa 出发经过若干座（含 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)。
输入输出样例
输入样例#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
说明
对于 20% 的数据 (n leq 1000, q leq 1000n≤1000,q≤1000)
对于 100% 的数据 (n leq 100000, m leq n, q leq 300000 n≤100000,m≤n,q≤300000)
题解：
首先，连通性可以用并查集维护
至于连接，暴力启发式合并就可以了
然后直接写splay
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<bitset>
#include<sstream>
#include<cstdlib>
#define QAQ int
#define TAT long long
#define OwO bool
#define ORZ double
#define F(i,j,n) for(QAQ i=j;i<=n;++i)
#define E(i,j,n) for(QAQ i=j;i>=n;--i)
#define MES(i,j) memset(i,j,sizeof(i))
#define MEC(i,j) memcpy(i,j,sizeof(j))
using namespace std;
const QAQ N=100005;
QAQ n,m,rot,fa[N];
struct data{
QAQ fa,son[2],val,size;
data(){
fa=0;son[1]=son[0]=0;val=0;size=0;
}
}tree[N];
queue<QAQ> q;
QAQ find(QAQ x){return fa[x]==x ? x : fa[x]=find(fa[x]);}
void push_up(QAQ o){tree[o].size=tree[tree[o].son[1]].size+tree[tree[o].son[0]].size+1;}
OwO get(QAQ o){return tree[tree[o].fa].son[1]==o;}
void rotate(QAQ o){
QAQ fa=tree[o].fa,ff=tree[fa].fa;
OwO pd=get(o);
if(ff) tree[ff].son[get(fa)]=o;
tree[o].fa=ff;
tree[fa].son[pd]=tree[o].son[1-pd];
tree[tree[o].son[1-pd]].fa=fa;
tree[fa].fa=o;tree[o].son[1-pd]=fa;
push_up(fa);push_up(o);
}
void splay(QAQ o,QAQ goal){
while(tree[o].fa!=goal){
QAQ fa=tree[o].fa,ff=tree[fa].fa;
if(ff!=goal) if(tree[fa].son[1]==o ^ tree[ff].son[1]==fa) rotate(o);
else rotate(fa);
rotate(o);
}
if(!goal) rot=o;
push_up(o);
}
void Insert(QAQ x){
QAQ t=rot;
while(1){
if(tree[x].val<tree[t].val) if(!tree[t].son[0]){
tree[t].son[0]=x;
tree[x].fa=t;
splay(x,0);
return ;
}
else t=tree[t].son[0];
else if(!tree[t].son[1]) {
tree[t].son[1]=x;
tree[x].fa=t;
splay(x,0);
return ;
}
else t=tree[t].son[1];
}
}
void Merge(QAQ x,QAQ y){
if(tree[x].size<tree[y].size) swap(x,y);
fa[y]=x;rot=x;
q.push(y);
while(q.size()){
QAQ t=q.front();q.pop();
if(tree[t].son[0]) q.push(tree[t].son[0]);
if(tree[t].son[1]) q.push(tree[t].son[1]);
tree[t].son[0]=tree[t].son[1]=0;
tree[t].size=1;
Insert(t);
}
splay(x,0);
}
QAQ K_th(QAQ o,QAQ x){
if(x>tree[o].size) return -1;
QAQ t=rot;
while(1){
if(tree[tree[t].son[0]].size>=x) t=tree[t].son[0];
else if(tree[tree[t].son[0]].size==x-1) return t;
else x-=(tree[tree[t].son[0]].size+1),t=tree[t].son[1];
}
}
QAQ main(){
scanf("%d%d",&n,&m);
F(i,1,n) scanf("%d",&tree[i].val),fa[i]=i;
rot=0;
F(i,1,m) {
QAQ x,y;
scanf("%d%d",&x,&y);
x=find(x);y=find(y);
if(x==y) continue;
splay(x,0);splay(y,0);
Merge(x,y);
}
scanf("%d",&m);
while(m--){
char c;
QAQ a,b;
cin>>c;scanf("%d%d",&a,&b);
if(c=='B'){
a=find(a);b=find(b);
splay(a,0);splay(b,0);
Merge(a,b);
}
else {
a=find(a);splay(a,0);
printf("%d
",K_th(a,b));
}
}
return 0;
}