课上写的,不知道错在哪里,求各位巨佬指教
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=114514;
struct node{
int l,r,val,rnd,size;
}tr[maxn];
int root,idx;
void newnode(int &x,int v){
idx++,x=idx,tr[x].val=v,tr[x].rnd=rand(),tr[x].size=1;
}
void pushup(int p){
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+1;
}
void split(int p,int v,int &x,int &y){
if(!p){
x=y=0;
return;
}
if(tr[p].val<v){
x=p;
split(tr[p].r,v,tr[p].r,y);
}else{
y=p;
split(tr[p].l,v,x,tr[p].l);
}
pushup(p);
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(tr[x].rnd<tr[y].rnd){
tr[x].r=merge(tr[x].r,y);
pushup(x);
return x;
}else{
tr[y].l=merge(x,tr[y].l);
pushup(y);
return y;
}
}
void insert(int v){
int x,y,z;
newnode(z,v);
split(root,v,x,y);
root=merge(merge(x,z),y);
}
void del(int v){
int x,y,z;
split(root,v,x,z);
split(x,v-1,x,y);
y=merge(tr[y].l,tr[y].r);
root=merge(merge(x,y),z);
}
int getrank(int v){
int x,y;
split(root,v-1,x,y);
int ans=tr[x].size+1;
root=merge(x,y);
return ans;
}
int getval(int root,int k){
if(k==tr[tr[root].l].size+1)return tr[root].val;
if(k<=tr[tr[root].l].size)return getval(tr[root].l,k);
return getval(tr[root].r,k-tr[tr[root].l].size-1);
}
int getpre(int v){
int x,y,s,ans;
split(root,v-1,x,y);
s=tr[x].size;
ans=getval(x,s);
root=merge(x,y);
return ans;
}
int getnxt(int v){
int x,y,ans;
split(root,v,x,y);
ans=getval(y,1);
root=merge(x,y);
return ans;
}
signed main(){
int n,op,v;
cin>>n;
for(int i=1;i<=n;i++){
cin>>op>>v;
if(op==1)insert(v);
else if(op==2)del(v);
else if(op==3)cout<<getrank(v)<<'\n';
else if(op==4)cout<<getval(root,v)<<'\n';
else if(op==5)cout<<getpre(v)<<'\n';
else cout<<getnxt(v)<<'\n';
}
return 0;
}
来不及写注释了。麻烦各位巨佬!