题目链接
第一次写(2017.11.7)：
#include<cstdio>
#include<cctype>
using namespace std;
const int N=1e5+5,INF=1e9;
int size,root,t[N],sz[N],son[N][2],fa[N],cnt[N];
inline int read()
{
int now=0,f=1;register char c=getchar();
for(;!isdigit(c);c=getchar())
if(c=='-') f=-1;
for(;isdigit(c);now=now*10+c-'0',c=getchar());
return now*f;
}
inline void Update(int rt)
{
sz[rt]= sz[son[rt][0]]+sz[son[rt][1]]+cnt[rt];
}
void Rotate(int x,int &k)
{
int a=fa[x],b=fa[a],l=(son[a][1]==x),r=l^1;
if(a==k) k=x;
else son[b][son[b][1]==a]=x;
fa[a]=x, fa[x]=b, fa[son[x][r]]=a,
son[a][l]=son[x][r], son[x][r]=a;
Update(a),Update(x);
}
void Splay(int x,int &rt)
{
int a,b;
while(x!=rt)
{
a=fa[x], b=fa[a];
if(a!=rt)
{
if((son[a][0]==x)^(son[b][0]==a)) Rotate(x,rt);
else Rotate(a,rt);
}
Rotate(x,rt);
}
}
void Insert(int k,int v)
{
int f=0;
while(k && t[k]!=v) f=k, k=son[k][v>t[k]];
if(k) ++cnt[k];
else
{
k=++size, sz[k]=cnt[k]=1, fa[k]=f, t[k]=v;
if(f) son[f][v>t[f]]=k;
}
Splay(k,root);
}
void Get_Rank(int k,int v)
{
if(!k) return;
while(son[k][v>t[k]] && t[k]!=v) k=son[k][v>t[k]];
Splay(k,root);
}
int Rank(int k,int x)
{
// ++x;//加了哨兵元素
//if(sz[k]<x) return 0;
while(1)
{
if(sz[son[k][0]]<x && sz[son[k][0]]+cnt[k]>=x) return k;
if(sz[son[k][0]]<x) x-=sz[son[k][0]]+cnt[k],k=son[k][1];
else k=son[k][0];
}
}
int Find(int v,int f)
{
Get_Rank(root,v);
if((t[root]>v && f)||(t[root]<v && !f)) return root;
int k=son[root][f];f^=1;
while(son[k][f]) k=son[k][f];
return k;
}
void Delete(int k,int v)
{
Get_Rank(root,v);
if(cnt[root]>1){--cnt[root],--sz[root];return;}
int x=root;
if(son[root][0] && son[root][1])
{
int k=son[root][1];root=k;
while(son[k][0]) k=son[k][0];
sz[k]+=sz[son[x][0]], fa[son[x][0]]=k, son[k][0]=son[x][0];
Splay(k,root);
}
else
root=son[root][0]+son[root][1];
fa[root]=0;
}
int main()
{
// freopen("testdata.in","r",stdin);
int n=read(),opt,x;
// Insert(root,-INF),Insert(root,INF);
while(n--)
{
opt=read(),x=read();
if(opt==1) Insert(root,x);
else if(opt==2) Delete(root,x);
else if(opt==3) Get_Rank(root,x), printf("%d\n",sz[son[root][0]]+1);
else if(opt==4) printf("%d\n",t[Rank(root,x)]);
else if(opt==5) printf("%d\n",t[Find(x,0)]);
else printf("%d\n",t[Find(x,1)]);
}
return 0;
}
第二次写(2017.12.3)：
#include<cstdio>
#include<cctype>
const int N=1e5+5;
int n,root,size,sz[N],cnt[N],t[N],son[N][2],fa[N];
inline int read()
{
int now=0,f=1;register char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);now=now*10+c-'0',c=getchar());
return now*f;
}
inline void Update(int rt)
{
sz[rt]=sz[son[rt][0]]+sz[son[rt][1]]+cnt[rt];
}
void Rotate(int x,int &k)
{
int a=fa[x],b=fa[a],l=son[a][1]==x,r=l^1;
if(a==k) k=x;
else son[b][son[b][1]==a]=x;
fa[x]=b, fa[a]=x, fa[son[x][r]]=a;
son[a][l]=son[x][r], son[x][r]=a;
Update(a),Update(x);
}
void Splay(int x,int &k)
{
while(x!=k)
{
int a=fa[x],b=fa[a];
if(a!=k)
{
if((son[a][0]==x)^(son[b][0]==a)) Rotate(x,k);
else Rotate(a,k);
}
Rotate(x,k);
}
}
void Insert(int v,int k)
{
int f=0;
while(k && t[k]!=v) f=k,k=son[k][v>t[k]];//v>t[k]!
if(k) ++cnt[k];
else
{
k=++size, sz[k]=cnt[k]=1, t[k]=v, fa[k]=f;
if(f) son[f][v>t[f]]=k;
}
Splay(k,root);
}
void Rank(int v,int k)
{
if(!k) return;//!
while(son[k][v>t[k]] && t[k]!=v) k=son[k][v>t[k]];
Splay(k,root);
}
void Delete(int v)
{
Rank(v,root);//!
// while(son[k][v>t[k]] && t[k]!=v) k=son[k][v>t[k]];//!
if(cnt[root]>1) {--cnt[root],--sz[root]; return;}//--sz[k]!
if(son[root][0] && son[root][1])//两种情况!
{
int tmp=root,k=son[root][1];
root=k;//root=k!
while(son[k][0]) k=son[k][0];
sz[k]+=sz[son[tmp][0]],//加sz!
fa[son[tmp][0]]=k, son[k][0]=son[tmp][0];
Splay(k,root);//!
}
else root=son[root][0]+son[root][1];
fa[root]=0;//!
// Splay(k,root);
}
int Get_Rank(int x,int k)
{
while(1)
{
if(sz[son[k][0]]<x && sz[son[k][0]]+cnt[k]>=x) return k;
if(sz[son[k][0]]<x) x-=sz[son[k][0]]+cnt[k],k=son[k][1];
else k=son[k][0];
}
}
int Find(int v,int f)
{
Rank(v,root);
if((t[root]>v && !f)||(t[root]<v && f)) return root;
int k=son[root][f^1];
while(son[k][f]) k=son[k][f];
return k;
}
int main()
{
// freopen("3369.in","r",stdin);
n=read();
int opt,x;
while(n--)
{
opt=read(),x=read();
if(opt==1) Insert(x,root);
else if(opt==2) Delete(x);
else if(opt==3) Rank(x,root),printf("%d\n",sz[son[root][0]]+1);
else if(opt==4) printf("%d\n",t[Get_Rank(x,root)]);
else if(opt==5) printf("%d\n",t[Find(x,1)]);
else printf("%d\n",t[Find(x,0)]);
}
return 0;
}
第三次写(2018.4.4)：（码风变化有点大啊）
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define MAXIN 500000
const int N=2e5+5;
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=gc()) if(c=='-') f=-1;
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
namespace Splay
{
#define lson son[x][0]
#define rson son[x][1]
int root,size,fa[N],son[N][2],sz[N],t[N],cnt[N];
inline void Update(int x){
sz[x]=sz[lson]+sz[rson]+cnt[x];
}
void Rotate(int x,int &k)
{
int a=fa[x],b=fa[a],l=son[a][1]==x,r=l^1;
if(k==a) k=x;
else son[b][son[b][1]==a]=x;
fa[a]=x, fa[x]=b, fa[son[x][r]]=a,
son[a][l]=son[x][r], son[x][r]=a;
Update(a);// Update(x);
}
void Splay(int x,int &k)
{
while(x!=k)
{
int a=fa[x],b=fa[a];
if(a!=k) (son[a][1]==x^son[b][1]==a)?Rotate(x,k):Rotate(a,k);
Rotate(x,k);
}
Update(x);
}
void Insert(int v,int k)
{
int f=0;
while(t[k]!=v&&k) f=k,k=son[k][v>t[k]];
if(k) ++cnt[k];
else{
k=++size, sz[k]=cnt[k]=1, t[k]=v, fa[k]=f;
if(f) son[f][v>t[f]]=k;
}
Splay(k,root);
}
void Rank(int v,int k)
{
// if(!k) return;
while(t[k]!=v && son[k][v>t[k]]) k=son[k][v>t[k]];
Splay(k,root);
}
void Delete(int v,int k)
{
Rank(v,root);
if(cnt[root]>1) --cnt[root],--sz[root];
else if(son[root][0]&&son[root][1])
{
int ls=son[root][0],k=son[root][1];
fa[root=k]=0;
while(son[k][0]) k=son[k][0];
fa[ls]=k, son[k][0]=ls;// sz[k]+=sz[ls];
Splay(k,root);
}
else root=son[root][0]^son[root][1],fa[root]=0;
}
int Get_Rank(int k,int x)
{
while(1)
{
if(sz[lson]<k && sz[lson]+cnt[x]>=k) return x;
if(sz[lson]<k) k-=sz[lson]+cnt[x],x=rson;
else x=lson;
}
}
int Find(int v,int w)
{
Rank(v,root);
if((t[root]>v&&!w)||(t[root]<v&&w)) return root;//!
int x=son[root][w^1];
while(son[x][w]) x=son[x][w];
return x;
}
}
using namespace Splay;
int main()
{
int n=read(),opt;
while(n--)
switch(opt=read())
{
case 1: Insert(read(),root); break;
case 2: Delete(read(),root); break;
case 3: Rank(read(),root),printf("%d\n",sz[son[root][0]]+1); break;
case 4: printf("%d\n",t[Get_Rank(read(),root)]); break;
case 5: printf("%d\n",t[Find(read(),1)]); break;
case 6: printf("%d\n",t[Find(read(),0)]); break;
}
return 0;
}