用权值线段树实现平衡树模板(P3369)那道题的时候，有离散数组node.val[]和原数组（应该是吧）b[]

问题在于,为何对于像是求前驱和后继这样在"真实的数组"中不存在的值,还要存进b[]中呢?例如在求$kth$时写 cout<<b[query_num(1,1,tot,node[i].val)]<<endl; 会不会输出前文提及的"不存在的值"?

完整代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int tree[4*N];
int push_up(int p){
	tree[p]=tree[p*2]+tree[p*2+1];
}
void update(int p,int l,int r,int x,int k){ //单点修改 
	if(l==r) {
		tree[p]+=k;
		return ;
	}
	int mid=(l+r)/2;
	if(x<=mid)  update(p*2,l,mid,x,k);
	else update(p*2+1,mid+1,r,x,k);
	push_up(p);
}
int query_rank(int p,int l,int r,int nl,int nr){
	if(nl<=l&&r<=nr) {
		return tree[p];
	}
	int mid=(l+r)/2,ans=0;
	if(nl<=mid) ans+=query_rank(p*2,l,mid,nl,nr);
	if(mid<nr) ans+=query_rank(p*2+1,mid+1,r,nl,nr);
	return ans;
}
int query_num(int p,int l,int r,int k){
	//查询第k小的数,但是返回下标 
	if(l==r){
		return l;
	}
	int mid=(l+r)/2;
	if(tree[p*2]>=k) return query_num(p*2,l,mid,k);
	else return query_num(p*2+1,mid+1,r,k-tree[p*2]);
}
int b[N*2],tot,n;
struct _node{
	int opt,val;
}node[N*2];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>node[i].opt>>node[i].val;
		if(node[i].opt==4) continue;
		b[++tot]=node[i].val;
	}
	sort(b+1,b+tot+1);
//	for(int i=1;i<=tot;i++) cout<<b[i]<<" ";
	tot=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++){
		if(node[i].opt!=4) node[i].val=lower_bound(b+1,b+tot+1,node[i].val)-b ;//离散化 
//		cout<<node[i].val<<endl; 
		//插入 x 数
		if(node[i].opt==1) update(1,1,tot,node[i].val,1);
		//删除 x 数(若有多个相同的数，因只删除一个)
		if(node[i].opt==2) update(1,1,tot,node[i].val,-1);
		//查询 x 数的排名(排名定义为比当前数小的数的个数 +1 )
		if(node[i].opt==3){
			if(node[i].val==1){ //防止出现1-1=0地情况 
				cout<<1<<endl;
				continue;
			}else{
				cout<<query_rank(1,1,tot,1,node[i].val-1)+1<<endl;
			}
		}
		//查询排名为 x 的数
		if(node[i].opt==4){
			cout<<b[query_num(1,1,tot,node[i].val)]<<endl;  //因为离散化了,还要回去 
		}
		//求x的前驱 
		if(node[i].opt==5){
			int rk=query_rank(1,1,tot,1,node[i].val-1);
			cout<<b[query_num(1,1,tot,rk)]<<endl;
		}
		//求x的后继 
		if(node[i].opt==6){
			int rk=query_rank(1,1,tot,1,node[i].val)+1;
			cout<<b[query_num(1,1,tot,rk)]<<endl;
		}
	}
	return 0;
}