以下代码为gpt4所写,只能获得20pts,求调
#include<bits/stdc++.h>
using namespace std;
struct node {
int l,r;
int val,key;
int size;
}fhq[1000000];
int cnt,root;
int New(int val) {
fhq[++cnt].val=val;
fhq[cnt].key=rand();
fhq[cnt].size=1;
fhq[cnt].l=fhq[cnt].r=0;
return cnt;
}
void update(int now) {
fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
void build() {
New(-2147483647);
New(2147483647);
root=1;
fhq[1].r=2;
update(1);
}
int getrank(int val) {
int ans=0,now=root;
while(now) {
if(val<=fhq[now].val) now=fhq[now].l;
else {
ans+=fhq[fhq[now].l].size+1;
now=fhq[now].r;
}
}
return ans+1;
}
int getnum(int rank) {
int now=root;
while(now) {
if(fhq[fhq[now].l].size+1==rank) break;
else if(fhq[fhq[now].l].size>=rank) now=fhq[now].l;
else {
rank-=fhq[fhq[now].l].size+1;
now=fhq[now].r;
}
}
return fhq[now].val;
}
int pre(int val) {
int ans=1,now=root;
while(now) {
if(fhq[now].val<val) {
ans=now;
now=fhq[now].r;
}
else now=fhq[now].l;
}
return fhq[ans].val;
}
int next(int val) {
int ans=2,now=root;
while(now) {
if(fhq[now].val>val) {
ans=now;
now=fhq[now].l;
}
else now=fhq[now].r;
}
return fhq[ans].val;
}
void split(int now,int val,int &x,int &y) {
if(!now) {
x=y=0;
return;
}
if(fhq[now].val<=val) {
x=now;
split(fhq[now].r,val,fhq[now].r,y);
}
else {
y=now;
split(fhq[now].l,val,x,fhq[now].l);
}
update(now);
}
void merge(int &now,int x,int y) {
if(!x||!y) {
now=x+y;
return;
}
if(fhq[x].key>fhq[y].key) {
now=x;
merge(fhq[now].r,fhq[x].r,y);
}
else {
now=y;
merge(fhq[now].l,x,fhq[y].l);
}
update(now);
}
void insert(int val) {
int x,y,z;
split(root,val,x,y);
z=New(val);
merge(x,x,z);
merge(root,x,y);
}
void del(int val) {
int x,y,z;
split(root,val-1,x,y);
split(y,val,y,z);
merge(y,fhq[y].l,fhq[y].r);
merge(root,x,y);
}
int main() {
int n;
cin>>n;
build();
for(int i=1;i<=n;i++) {
int opt,x;
cin>>opt>>x;
if(opt==1) insert(x);
if(opt==2) del(x);
if(opt==3) cout<<getrank(x)-1<<endl;
if(opt==4) cout<<getnum(x+1)<<endl;
if(opt==5) cout<<pre(x)<<endl;
if(opt==6) cout<<next(x)<<endl;
}
return 0;
}