就离谱,后面的都过了,错的竟然是前面两个点
#include <bits/stdc++.h>
using namespace std;
const long long N=100005,INF=100000000;
struct node
{
long long l,r;
long long key,val;
long long cnt,siz;
}tr[N*4];
long long root,idx;
long long getnode(long long key)
{
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].cnt=1;
tr[idx].siz=1;
return idx;
}
void pushup(long long u)
{
tr[u].siz=tr[tr[u].l].siz+tr[u].cnt+tr[tr[u].r].siz;
}
void build()
{
getnode(-INF);
getnode(INF);
root=1;
tr[1].r=2;
pushup(root);
}
void zig(long long &u)
{
long long v=tr[u].l;
tr[u].l=tr[v].r;
tr[v].r=u;
u=v;
pushup(tr[u].r);
pushup(u);
}
void zag(long long &u)
{
long long v=tr[u].r;
tr[u].r=tr[v].l;
tr[v].l=u;
u=v;
pushup(tr[u].l);
pushup(u);
}
void insert(long long &u,long long key)
{
if(!u) u=getnode(key);
else if(tr[u].key==key) tr[u].cnt++;
else if(tr[u].key > key)
{
insert(tr[u].l,key);
if(tr[tr[u].l].val>tr[u].val) zig(u);
}
else
{
insert(tr[u].r,key);
if(tr[tr[u].r].val > tr[u].val) zag(u);
}
pushup(u);
}
void remove(long long &u,long long key)
{
if(!u) return;
if(tr[u].key == key)
{
if(tr[u].cnt > 1) tr[u].cnt--;
else if(tr[u].l || tr[u].r)
{
if(!tr[u].r || tr[tr[u].l].val > tr[tr[u].r].val)
{
zig(u);
remove(tr[u].r,key);
}
else
{
zag(u);
remove(tr[u].l,key);
}
}
else u=0;
}
else
{
if(tr[u].key>key) remove(tr[u].l,key);
else remove(tr[u].r,key);
}
pushup(u);
}
long long getrank(long long u,long long key)
{
if(!u) return 0;
if(tr[u].key == key) return tr[tr[u].l].siz+1;
if(tr[u].key > key) return getrank(tr[u].l,key);
return tr[tr[u].l].siz + tr[u].cnt + getrank(tr[u].r,key);
}
long long getkey(long long u,long long rank)
{
if(!u) return INF;
if(tr[tr[u].l].siz >= rank) return getkey(tr[u].l,rank);
if(tr[tr[u].l].siz + tr[u].cnt >= rank) return tr[u].key;
return getkey(tr[u].r,rank-tr[tr[u].l].siz-tr[u].cnt);
}
long long getprev(long long u,long long key)
{
if(!u) return -INF;
if(tr[u].key >= key) return getprev(tr[u].l,key);
return max(tr[u].key,getprev(tr[u].r,key));
}
long long getnxt(long long u,long long key)
{
if(!u) return INF;
if(tr[u].key <= key) return getnxt(tr[u].r,key);
return min(tr[u].key,getnxt(tr[u].l,key));
}
int main()
{
build();
long long n;
scanf("%lld",&n);
while(n--)
{
long long opt,x;
scanf("%lld%lld",&opt,&x);
if(opt==1) insert(root,x);
else if(opt==2) remove(root,x);
else if(opt==3) printf("%lld\n",getrank(root,x)-1);
else if(opt==4) printf("%lld\n",getkey(root,x+1));
else if(opt==5) printf("%lld\n",getprev(root,x));
else printf("%lld\n",getnxt(root,x));
}
return 0;
}