说不上全，想起来就添
平衡树
splay
#include<bits/stdc++.h>
using namespace std;
#define il inline
const int DWDB_221E=122300;
#define Croll(i,l,r) for(int i=l;i<=r;++i)
//////////
namespace sbtree
{
#define lid tr[x].son[0]
#define rid tr[x].son[1]
int root,tot;
struct stellaris
{
int fa;//父节点
int son[2];//两个儿子节点
int w,cnt;//权值 及其 出现次数
int siz;//所在子树大小
}tr[DWDB_221E];
il int upper();//前驱
il int lower();//后驱
il void del(int);//删除
il void insert(int);//增加节点
il int find_rk(int);//查询排名
il void clear(int);//清空该节点
il void splay(int);//将x转到根节点
il void update(int);//更新整棵子树大小
il int find_n(int);//找排名为x的点的权
il void rotate(int);//将x与其父节点旋转
il bool relate(int);//查询与其父节点关系
}
using namespace sbtree;
//////////
il int read();
//////////
int main()
{
#ifdef ONLINEJUDGE
freopen("inn","r",stdin);
freopen("outt","w",stdout);
#endif
int n=read();
Croll(ACT4,1,n)
{
// cout<<ACT4<<" ;( "<<root<<endl;
int act=read(),x=read();
if(act==1)insert(x);
else if(act==2)del(x);
else if(act==3)cout<<find_rk(x)<<endl;
else if(act==4)cout<<find_n(x)<<endl;
else if(act==5)
{
insert(x);
cout<<tr[upper()].w<<endl;
del(x);
}
else if(act==6)
{
insert(x);
cout<<tr[lower()].w<<endl;
del(x);
}
}
return 0;
}
//////////
namespace sbtree
{
il void clear(int x)
{
tr[x].w=0;tr[x].fa=0;
tr[x].siz=0;tr[x].cnt=0;
lid=0;rid=0;return;
}
il bool relate(int x)
{
return tr[tr[x].fa].son[1]==x;
}
il void update(int x)
{
if(x)
{
tr[x].siz=tr[x].cnt;
if(lid)tr[x].siz+=tr[lid].siz;
if(rid)tr[x].siz+=tr[rid].siz;
}
return;
}
il void rotate(int x)
{
int fat=tr[x].fa,gfa=tr[fat].fa,h=relate(x);
tr[fat].son[h]=tr[x].son[h^1];
tr[tr[fat].son[h]].fa=fat;
tr[x].son[h^1]=fat;
tr[fat].fa=x;tr[x].fa=gfa;
if(gfa){tr[gfa].son[tr[gfa].son[1]==fat]=x;}
update(fat);update(x);
}
il void splay(int x)
{
for(int f;f=tr[x].fa;rotate(x))
{
if(tr[f].fa)
rotate((relate(x)==relate(f)?f:x));
}
root=x;
}
il void insert(int x)
{
if(!root)
{
root=++tot;
tr[tot].son[0]=tr[tot].son[1]=tr[tot].fa=0;
tr[tot].siz=tr[tot].cnt++;
tr[tot].w=x;
return;
}
int now=root,fat=0;
while(1)
{
if(x==tr[now].w)
{
tr[now].cnt++;
update(now);
update(fat);
splay(now);
break;
}
fat=now;now=tr[now].son[tr[now].w<x];
if(!now)
{
tot++;
tr[tot].son[0]=tr[tot].son[1]=0;
tr[tot].fa=fat;
tr[tot].siz=tr[tot].cnt=1;
tr[fat].son[tr[fat].w<x]=tot;
tr[tot].w=x;
update(fat);
splay(tot);
break;
}
}
}
il int find_n(int x)
{
int now=root;
while(1)
{
if(tr[now].son[0] && x<=tr[tr[now].son[0]].siz)
now=tr[now].son[0];
else
{
int tmp=0;
if(tr[now].son[0])
tmp+=tr[tr[now].son[0]].siz;
tmp+=tr[now].cnt;
if(x<=tmp){return tr[now].w;}
x-=tmp;now=tr[now].son[1];
}
}
}
il int find_rk(int x)
{
int now=root,ans=0;
while(1)
{
if(x<tr[now].w)
now=tr[now].son[0];
else
{
if(tr[now].son[0])
ans+=tr[tr[now].son[0]].siz;
if(x==tr[now].w){splay(now);return ans+1;}
ans+=tr[now].cnt;now=tr[now].son[1];
}
}
}
il int upper()
{
int now=tr[root].son[0];
while(tr[now].son[1])
now=tr[now].son[1];
return now;
}
il int lower()
{
int now=tr[root].son[1];
while(tr[now].son[0])
now=tr[now].son[0];
return now;
}
il void del(int x)
{
int D4C=find_rk(x);
// cout<<"^_^"<<x<<endl;
// cout<<tr[root].son[0]<<endl;
// cout<<tr[root].son[1]<<endl;
if(tr[root].cnt>1)
{tr[root].cnt--;update(root);return;}
if(!tr[root].son[0] && !tr[root].son[1])
{clear(root);root=0;return;}
if(!tr[root].son[0])
{
int now=tr[root].son[1];
tr[now].fa=0;clear(root);
root=now;
return;
}
else if(!tr[root].son[1])
{
int now=tr[root].son[0];
tr[now].fa=0;clear(root);
root=now;
return;
}
int left=upper(),old=root;
splay(left);
tr[root].son[1]=tr[old].son[1];
tr[tr[old].son[1]].fa=root;
clear(old);
update(root);
}
}
il int read()
{
int f=1,x=0;char w=getchar();
while(w<'0' || w>'9')
{if(w=='-')f=-1;w=getchar();}
while('0'<=w && w<='9')
{x=(x<<1)+(x<<3)+(w^48);w=getchar();}
return f*x;
}
---
FHQ
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define lol long long
const int DWDB_221E=1223000;
#define Croll(i,l,r) for(int i=l;i<=r;++i)
#define Troll(i,l,r) for(int i=l;i>=r;--i)
//////////
namespace FHQ
{
#define ls tr[x].son[0]
#define rs tr[x].son[1]
int root,tot;
struct stellaris
{
int rd;
int son[2];
int num,siz;
}tr[DWDB_221E];
void add(int);//加点
void del(int);//删点
void lower(int);//后驱
void upper(int);//前驱
void find_rk(int);//排名
il void update(int);//更新
int find_n(int,int);//找排名
il int merge(int,int);//合并
il void split(int,int,int&,int&);//分离
}using namespace FHQ;
//////////
il int read();
//////////
int main()
{
srand(time(0));
}
//////////
namespace FHQ
{
void add(int num)
{
int lrt,rrt;
tr[++tot].num=num;
tr[tot].siz=1;
tr[tot].rd=rand();
split(root,num,lrt,rrt);
root=merge(merge(lrt,tot),rrt);
return;
}
void del(int num)
{
int lrt,rrt,mrt;
split(root,num,lrt,rrt);
split(lrt,num-1,lrt,mrt);
mrt=merge(tr[mrt].son[0],tr[mrt].son[1]);
root=merge(merge(lrt,mrt),rrt);
return;
}
void lower(int num)
{
int lrt,rrt;
split(root,num-1,lrt,rrt);
int now=lrt;
while(tr[now].son[1])
now=tr[now].son[1];
root=merge(lrt,rrt);
cout<<tr[now].num<<endl;
return;
}
void upper(int num)
{
int lrt,rrt;
split(root,num,lrt,rrt);
int now=rrt;
while(tr[now].son[0])
now=tr[now].son[0];
root=merge(lrt,rrt);
cout<<tr[now].num<<endl;
return;
}
void find_rk(int num)
{
int lrt,rrt;
split(root,num-1,lrt,rrt);
cout<<tr[lrt].siz+1<<endl;
root=merge(lrt,rrt);
return;
}
il void update(int x)
{
if(!x)return;
tr[x].siz=tr[ls].siz+tr[rs].siz+1;
return;
}
int find_n(int x,int num)
{
if(tr[ls].siz+1==num)return tr[x].num;
if(tr[ls].siz>=num)return find_n(ls,num);
if(tr[ls].siz<num)return find_n(rs,num-tr[ls].siz-1);
return 114514;
}
il int merge(int x,int y)
{
if(!x || !y)return x+y;
if(tr[x].rd<tr[y].rd)
{
rs=merge(rs,y);
update(x);
return x;
}
else
{
tr[y].son[0]=merge(x,tr[y].son[0]);
update(y);
return y;
}
}
il void split(int x,int mid,int& lrt,int& rrt)
{
if(!x)lrt=rrt=0;
else
{
if(tr[x].num<=mid)
{
lrt=x;
split(rs,mid,rs,rrt);
}
else
{
rrt=x;
split(ls,mid,lrt,ls);
}
update(x);
}
return;
}
}
//////////
il int read()
{
int f=1,x=0;char w=getchar();
while(w<'0'||w>'9')
{if(w=='-')f=-1;w=getchar();}
while('0'<=w && w<='9')
{x=(x<<3)+(x<<1)+(w^48);w=getchar();}
return f*x;
}