样例未过,RE了。
#include <bits/stdc++.h>
#include <unistd.h>
#define ll long long
#define ull unsigned long long
#define FOR(i,l,r) for(int i=l;i<=r;++i)
#define ROF(i,r,l) for(int i=r;i>=l;--i)
#define mkp make_pair
#define fr first
#define se second
using namespace std;
const int N=2e5+10;
int n,k,tot,root;
struct Node {
int ls,rs;
int val,key,siz;
}t[N];
void push_up(int p) {
t[p].siz=t[t[p].ls].siz+t[t[p].rs].siz+1;
}
void Spilt(int p,int x,int &l,int &r) {
if(!p) return (void)(l=r=0);
if(t[p].val<=x) l=p,Spilt(t[p].rs,x,t[p].rs,r);
else r=p,Spilt(t[p].ls,x,l,t[p].ls);
push_up(p);
}
int Merge(int l,int r) {
if(!l||!r) return l+r;
if(t[l].key<=t[r].key) return t[r].ls=Merge(l,t[r].ls),push_up(r),r;
else return t[l].rs=Merge(t[l].rs,r),push_up(l),l;
}
void Make(int x) {
t[++tot]={0,0,x,rand(),1};
}
int Insert(int x) {
int l,r;
Spilt(root,x,l,r),Make(x);
root=Merge(Merge(l,tot),r);
return tot;
}
int Erase(int x) {
int l,r,mid;
Spilt(root,x,l,r);
Spilt(l,x-1,l,mid);
mid=Merge(t[mid].ls,t[mid].rs);
return root=Merge(Merge(l,mid),r);
}
int kth(int p,int k) {
if(t[t[p].ls].siz+1==k) return p;
if(k<=t[t[p].ls].siz) return kth(t[p].ls,k);
return kth(t[p].rs,k-t[t[p].ls].siz-1);
}
int getid(int x) {
int l,r;
Spilt(root,x-1,l,r);
int res=t[l].siz+1;
root=Merge(l,r);
return res;
}
int lst(int x) {
int l,r;
Spilt(root,x-1,l,r);
int res=t[kth(l,t[l].siz)].val;
root=Merge(l,r);
return res;
}
int nxt(int x) {
int l,r;
Spilt(root,x,l,r);
int res=t[kth(r,1)].val;
root=Merge(l,r);
return res;
}
int main() {
// srand(time(0));
cin>>n;
while(n--) {
int op,x;
cin>>op>>x;
if(op==1) Insert(x);
if(op==2) Erase(x);
if(op==3) cout<<getid(x)<<"\n";
if(op==4) cout<<t[kth(root,x)].val<<"\n";
if(op==5) cout<<lst(x)<<"\n";
if(op==6) cout<<nxt(x)<<"\n";
}
return 0;
}