数组的 -1 位置是内存中存储数组开头的前一个位置，这个位置是不确定的值，不同编译器可能有不同结果
by Michaellg @ 2023-10-05 12:21:17
但是我交了很多发，都是AC了，这一点不知道能不能排除随机访问到非法位置的可能性
而且访问到-1不应该直接RE掉吗
就是这点很奇怪啊，洛谷评测机自己自适应了？
by SinCircle @ 2023-10-05 12:35:29
同问
不开O2全AC 开O2全MLE
代码如下
```cpp
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n,m,q,cnt,p[MAXN],root[MAXN],fa[MAXN],bac[MAXN],ans;
struct sgtree{
int lson,rson,sum;
} tr[MAXN<<5];
inline int build(int l,int r,int val){
int now=++cnt;
tr[now].sum=1;
if(l==r) return now;
int mid=(l+r)>>1;
if(val<=mid) tr[now].lson=build(l,mid,val);
else tr[now].rson=build(mid+1,r,val);
return now;
}
inline int get(int x){
if(fa[x]==x) return x;
return fa[x]=get(fa[x]);
}
inline int merg(int pl,int pr,int l,int r){
if(!(pl&&pr))return pl|pr;
tr[pr].sum+=tr[pl].sum;
int mid=(l+r)>>1;
tr[pr].lson=merg(tr[pl].lson,tr[pr].lson,l,mid);
tr[pr].rson=merg(tr[pl].rson,tr[pr].rson,mid+1,r);
return pr;
}
inline int query(int p,int l,int r,int k){
if(!p) return -1;
if(l==r) return l;
int x=tr[tr[p].lson].sum,mid=(l+r)>>1;
if(x>=k) query(tr[p].lson,l,mid,k);
else query(tr[p].rson,mid+1,r,k-x);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
bac[p[i]]=i;
}
for(int i=1;i<=n;i++){
fa[i]=i;
root[i]=build(1,n,p[i]);
}
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
x=get(x);
y=get(y);
merg(root[x],root[y],1,n);
fa[x]=y;
}
scanf("%d",&q);
for(int i=1;i<=q;i++){
char op[2];
int x,y;
scanf("%s%d%d",op,&x,&y);
if(op[0]=='B'){
x=get(x);
y=get(y);
merg(root[x],root[y],1,n);
fa[x]=y;
}
else if(op[0]=='Q'){
x=get(x);
ans=query(root[x],1,n,y);
else printf("%d\n",bac[ans]);
}
}
return 0;
}
```
~~会长的码就是写得比我好看~~
by 推翻暴政 @ 2023-10-09 20:29:46
下标本质是指针加减，如果没修改奇怪东西一般没事，好像 $\texttt{linux}$ 有时候会放过去（吧。打开 `-fsanitize=address` 运行时就会报错了。
by N2MENT @ 2023-11-13 19:45:49
@[推翻暴政](/user/448555) 您的query函数中要改成这样就没事了。
```cpp
inline int query(int p,int l,int r,int k){
if(!p) return -1;
if(l==r) return l;
int x=tr[tr[p].lson].sum,mid=(l+r)>>1;
if(x>=k) return query(tr[p].lson,l,mid,k);
else return query(tr[p].rson,mid+1,r,k-x);
}
```
原因是：因为返回值为 int 的函数没有返回值所以挂了。
by Hoks @ 2024-02-01 12:24:30
@[Hoks](/user/551100) thx
by 推翻暴政 @ 2024-03-01 15:06:23