一、洛谷普通平衡树模板题。。。。题目不好复制。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const double alpha=0.75;
const int maxn=100100;
const int inf=0x3f3f3f3f;
struct node
{
int val;
int lc,rc;
int h;
int si;
}t[maxn];
int tot,root;
void pushup(int p)
{
t[p].h=max(t[t[p].lc].h,t[t[p].rc].h)+1;
t[p].si=t[t[p].lc].si+t[t[p].rc].si+1;
}
int getb(int p)
{
return t[t[p].lc].h-t[t[p].rc].h;
}
int newnode(int x)
{
int p=++tot;
t[p].lc=t[p].rc=0;
t[p].h=t[p].si=1;
t[p].val=x;
return p;
}
void R(int &p)
{
int q=t[p].lc;
t[p].lc=t[q].rc;
t[q].rc=p;
p=q;
pushup(t[p].rc);
pushup(p);
}
void L(int &p)
{
int q=t[p].rc;
t[p].rc=t[q].lc;
t[q].lc=p;
p=q;
pushup(t[p].lc);
pushup(p);
}
void RL(int &p)
{
R(t[p].rc);
L(p);
}
void LR(int &p)
{
L(t[p].lc);
R(p);
}
void lmax(int &p)
{
if(getb(p)==2)
{
if(getb(t[p].lc)==1)
R(p);
else if(getb(t[p].lc)==-1)
{
LR(p);
}
}
}
void rmax(int &p)
{
if(getb(p)==-2)
{
if(getb(t[p].rc)==-1)
L(p);
else if(getb(t[p].rc)==1)
RL(p);
}
}
int getmin(int p)
{
while(t[p].lc) p=t[p].lc;
return p;
}
int getmax(int p)
{
while(t[p].rc) p=t[p].rc;
return p;
}
void _insert(int &now,int val)
{
if(!now)
{
now=newnode(val);
return ;
}
if(val<t[now].val)
{
_insert(t[now].lc,val);
lmax(now);
}
else
{
_insert(t[now].rc,val);
rmax(now);
}
pushup(now);
}
void del(int &p,int x)
{
if(x<t[p].val)
{
del(t[p].lc,x);
rmax(p);
}
else if(x>t[p].val)
{
del(t[p].rc,x);
lmax(p);
}
else
{
if(t[p].lc&&t[p].rc)
{
int q=getmax(t[p].lc);
t[p].val=t[q].val;
del(t[p].lc,t[q].val);
rmax(p);
}
else
{
if(t[p].lc) p=t[p].lc;
else p=t[p].rc;
return ;
}
}
pushup(p);
}
int get_rank(int x)
{
int now=root,ans=0;
while(now)
{
if(t[now].val<x) ans+=t[t[now].lc].si+1,now=t[now].rc;
else now=t[now].lc;
}
return ans+1;
}
int get_val(int k)
{
int now=root;
while(1)
{
if(t[t[now].lc].si+1==k) return t[now].val;
else if(t[t[now].lc].si>=k) now=t[now].lc;
else k-=t[t[now].lc].si+1,now=t[now].rc;
}
}
int get_front(int x)
{
int now=root,ans=-inf;
while(now)
{
if(t[now].val<x) ans=max(ans,t[now].val),now=t[now].rc;
else now=t[now].lc;
}
return ans;
}
int get_behind(int x)
{
int now=root,ans=inf;
while(now)
{
if(t[now].val>x) ans=min(ans,t[now].val),now=t[now].lc;
else now=t[now].rc;
}
return ans;
}
int main(void)
{
int n;
scanf("%d",&n);
int pos,x;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&pos,&x);
if(pos==1)
_insert(root,x);
else if(pos==2)
del(root,x);
else if(pos==3)
printf("%d\n",get_rank(x));
else if(pos==4)
printf("%d\n",get_val(x));
else if(pos==5)
printf("%d\n",get_front(x));
else if(pos==6)
printf("%d\n",get_behind(x));
}
return 0;
}