@[PCCP](/user/310773)
## ~~你这个代码是真永无乡啊~~
首先在split函数中, **请注意x和y是传引用** ,而不能修改原pos的值。
第二处问题在main函数最后的操作 $Q$ 中。你的字符串读取有误,推荐使用以下格式:
```cpp
...
int op[2]; int x, y;
scanf("%s%d%d", op, &x, &y);
if(op[0] == 'B')
...
```
---
由于您的代码异常抽象,可能修改后还有其他细枝末节的问题,在此贴出改动最少的AC代码供可能的参考:
```cpp
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
const int N=1e6+10;
int n,m,q;
struct fhq{
int fa[N],tot=0,ch[N][2],val[N],siz[N],key[N];
int find(int x){
if(fa[x]==x){
return x;
}
return fa[x]=find(fa[x]);
}
int newnode(int k){
++tot;
val[tot]=k;
siz[tot]=1;
key[tot]=rand();
return tot;
}
void pushup(int pos){
siz[pos]=siz[ch[pos][0]]+siz[ch[pos][1]]+1;
}
void split(int pos,int k,int &x,int &y){
if(!pos){
x=y=0;
return;
}
else if(val[pos]<=k){
x=pos;
split(ch[x][1],k,ch[x][1],y);//1
}
else{
y=pos;
split(ch[y][0],k,x,ch[y][0]);
}
pushup(pos);
}
int merge(int x,int y){
if(!x||!y){
return x+y;
}
if(key[x]<key[y]){
ch[x][1]=merge(ch[x][1],y);
pushup(x);
return x;
}
else{
ch[y][0]=merge(x,ch[y][0]);
pushup(y);
return y;
}
}
int kth(int pos,int rank){
if(rank<=siz[ch[pos][0]]){
return kth(ch[pos][0],rank);
}
else if(rank==siz[ch[pos][0]]+1){
return pos;
}
else{
return kth(ch[pos][1],rank-siz[ch[pos][0]]-1);
}
}
void insert(int pos,int &rt){
int x,y;
split(rt,val[pos],x,y);
rt=merge(merge(x,pos),y);//?
}
void qfshb(int pos,int &rt){//?
if(!pos){
return;
}
qfshb(ch[pos][0],rt);
qfshb(ch[pos][1],rt);
ch[pos][0]=ch[pos][1]=0;
//siz[pos]=1; //?
insert(pos,rt);
}
int hb(int x,int y){
int rt1=fa[x],rt2=fa[y];
qfshb(rt1,rt2);
return rt2;
}
}tr;
int main(){
srand(time(0));
scanf("%d%d",&n,&m);
char opt;
int x,y;
for(int i=1;i<=n;i++){
scanf("%d",&x);
tr.newnode(x);
tr.fa[i]=i;
}
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
int fx=tr.find(x),fy=tr.find(y);
if(fx!=fy){
int ff = tr.hb(x, y);
tr.fa[fx] = tr.fa[fy] = tr.fa[ff] = ff;
}
}
scanf("%d",&q);
for(int i=1;i<=q;i++){
char op[2];
scanf("%s%d%d", op, &x, &y);
if(op[0]=='B'){
int fx=tr.find(x),fy=tr.find(y);
if(fx!=fy){
int ff = tr.hb(x, y);
tr.fa[fx] = tr.fa[fy] = tr.fa[ff] = ff;
}
}
else{
int fx=tr.find(x);
if(tr.siz[fx]<y){
printf("-1\n");
}
else{
printf("%d\n",tr.kth(fx,y));
}
}
}
}
```
---
**~~我既然把这段话放到最后,就证明关注不是那么重要,对吧~~**
by newamnesia @ 2023-05-05 16:37:23
修正一下,第一条是我
的问题,您没有错/kk
~~怪不得我调了那么长时间~~
by newamnesia @ 2023-05-05 17:43:03
@[newamnesia](/user/753440) 万分感谢!!!
by PCCP @ 2023-05-05 19:09:03