呸。。MLE
by moye到碗里来 @ 2018-04-11 20:42:28
@[moye到碗里来](/space/show?uid=52576) 所以，，，怎么改。。
by Brioche @ 2018-08-15 20:17:43
@[Brioche](/space/show?uid=61672) 我找一下。。好久以前的题了。。
by moye到碗里来 @ 2018-08-15 20:18:37
```
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 10;
inline int read(){
int x = 0,f = 1;char ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x*10 + ch - '0';ch = getchar();}
return x*f;
}
int fa[MAXN+100];
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
struct node{
int num,poi;
node *ls,*rs;
node(int n,int p,node *l,node *r):num(n),poi(p),ls(l),rs(r) {}
node(){}
}*rt[MAXN],pool[MAXN * 30];
inline node *NewNode(int poi){
static int cnt = 0;pool[cnt] = node(0,poi,NULL,NULL);
return &pool[cnt++];
}
void merge(node *x,node *y){
x->num += y->num;
if(y->ls != NULL){
if(x->ls == NULL)x->ls = y->ls;
else merge(x->ls,y->ls);
}
if(y->rs != NULL){
if(x->rs == NULL)x->rs = y->rs;
else merge(x->rs,y->rs);
}
}
void add(node *rt,int l,int r,int x,int p){
rt->num += 1;
int mid = (l + r) >> 1;
if(l == r)rt->poi = p;
if(l < r)
{
if(mid >= x){
if(rt->ls == NULL)rt->ls = NewNode(0);
add(rt->ls,l,mid,x,p);
}
else{
if(rt->rs == NULL)rt->rs = NewNode(0);
add(rt->rs,mid + 1,r,x,p);
}
}
return ;
}
int query(node *rt,int l,int r,int k){
if(rt->num < k)return -1;
if(l == r)return rt->poi;
if(l < r){
int mid = (l + r) >> 1;
int x = rt->ls == NULL ? 0 : rt->ls->num;
if(x >= k)return query(rt->ls,l,mid,k);
else return query(rt->rs,mid + 1,r,k - x);
}
}
int n,m;
int main()
{
//freopen("neverland9.in","r",stdin);
//freopen("1.out","w",stdout);
n = read();m = read();
for(int i = 1; i <= n; i++){
fa[i] = i;int a = read();rt[i] = NewNode(0);
add(rt[i],1,100005,a,i);
}
for(int i = 1; i <= m; i++){
int u = read(),v =read();
int a = find(u),b = find(v);
if(a == b)continue;
merge(rt[a],rt[b]);
fa[b] = a;
}
int q = read();
for(int i = 1; i <= q; i++){
char a;int x,y;
a = getchar();
while(a < 'A' || a > 'Z')a = getchar();
scanf("%d %d",&x,&y);
if(a == 'B'){
int a = find(x),b = find(y);
if(a == b)continue;
merge(rt[a],rt[b]);
fa[b] = a;
}
else{
printf("%d\n",query(rt[find(x)],1,100005,y));
}
}
}
```
by moye到碗里来 @ 2018-08-15 20:19:13
应该是我fa数组开小了。
by moye到碗里来 @ 2018-08-15 20:20:42
moye到碗里来 QAQ我也写的treap，还查了你的代码，但是不知道改哪里啊。。
by Brioche @ 2018-08-15 20:20:48
@[moye到碗里来](/space/show?uid=52576)
by Brioche @ 2018-08-15 20:21:04
@[Brioche](/space/show?uid=61672) 这题我用的不是treap啊。。是可合并线段树。
by moye到碗里来 @ 2018-08-15 20:22:01
@[moye到碗里来](/space/show?uid=52576) 尴尬。。看错了。。主观带入了
by Brioche @ 2018-08-15 20:32:11