SPLAY
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 1000005
using namespace std;
int ch[N][2],f[N],size[N],cnt[N],key[N],root,sz;
inline void clear(int x){
ch[x][0]=ch[x][1]=f[x]=size[x]=cnt[x]=key[x]=0;
}
inline bool get(int x){
return ch[f[x]][1]==x;
}
inline void update(int x){
if(x){
size[x]=cnt[x];
if(ch[x][0]) size[x]+=size[ch[x][0]];
if(ch[x][1]) size[x]+=size[ch[x][1]];
}
}
inline void rotate(int x){
int p=f[x],g=f[p],wz=get(x);
ch[p][wz]=ch[x][wz^1];
if(ch[p][wz]) f[ch[p][wz]]=p;
ch[x][wz^1]=p;
f[p]=x; f[x]=g;
if(g) ch[g][ch[g][1]==p]=x;
update(p); update(x);
}
inline void splay(int x)
{
for(int fa;fa=f[x];rotate(x))
if(f[fa])
rotate((get(x)==get(fa))?fa:x);
root=x;
}
inline void insert(int x){
if(root==0){
sz++; ch[sz][0]=ch[sz][1]=f[sz]=0;
size[sz]=cnt[sz]=1; key[sz]=x; root=sz;
return ;
}
int now=root,fa=0;
while(1){
if(x==key[now]){
cnt[now]++;update(now);
update(fa); splay(now);
break;
}
fa=now; now=ch[fa][key[fa]<x];
if(now==0){
sz++; f[sz]=fa; ch[sz][0]=ch[sz][1]=0;
ch[fa][key[fa]<x]=sz; size[sz]=cnt[sz]=1;
key[sz]=x; update(fa); splay(sz);
break;
}
}
}
inline int rank(int x){
int now=root,ans=0;
while(1){
if(x<key[now])
now=ch[now][0];
else{
ans+=(ch[now][0]?size[ch[now][0]]:0);
if(x==key[now]){ splay(now); return ans+1; }
ans+=cnt[now]; now=ch[now][1];
}
}
}
inline int find(int x){
int now=root;
while(1){
if(ch[now][0]&&x<=size[ch[now][0]]) now=ch[now][0];
else{
int temp=(ch[now][0]?size[ch[now][0]]:0)+cnt[now];
if(x<=temp) return key[now];
x-=temp; now=ch[now][1];
}
}
}
inline int pre(){
int now=ch[root][0];
while(ch[now][1]) now=ch[now][1];
return now;
}
inline int next(){
int now=ch[root][1];
while(ch[now][0]) now=ch[now][0];
return now;
}
inline void del(int x){
int num=rank(x);
if(cnt[root]>1){cnt[root]--; size[root]--; return;}
if(!ch[root][0]&&!ch[root][1]){clear(root); root=0; return ;}
if(!ch[root][0]){
int old=root; root=ch[root][1];
f[root]=0; clear(old);
return ;
}
if(!ch[root][1]){
int old=root; root=ch[root][0];
f[root]=0; clear(old);
return ;
}
int big=pre(),old=root; splay(big);
ch[root][1]=ch[old][1]; f[ch[root][1]]=root;
clear(old); update(root);
}
int main()
{
int n,opt,x;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&opt,&x);
if(opt==1) insert(x);
if(opt==2) del(x);
if(opt==3) printf("%d
",rank(x));
if(opt==4) printf("%d
",find(x));
if(opt==5){
insert(x);
printf("%d
",key[pre()]);
del(x);
}
if(opt==6){
insert(x);
printf("%d
",key[next()]);
del(x);
}
}
return 0;
}
TREAP
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#include <ctime>
#define size(a) ((a!=NULL)?(a)->size:0)
using namespace std;
struct Node{
Node *ch[2];
int key,size,num,tot;
Node(int x=0){
key=rand();num=x;size=tot=1;
memset(ch,0,sizeof ch);
}
void* operator new (size_t);
void operator delete (void *p);
}*root,*C,*M;
vector<Node*> q;
void* Node :: operator new (size_t){
if(C==M){
C=new Node[1<<15];
M=C+(1<<15);
}
return C++;
}
void Node :: operator delete (void *p){
q.push_back((Node*)p);
}
void pushup(Node *now){
if(!now) return;
now->size=size(now->ch[0])+size(now->ch[1])+now->tot;
}
void rot(Node *&now,int wh){
Node *son=now->ch[wh];
now->ch[wh]=son->ch[wh^1]; pushup(now);
son->ch[wh^1]=now; pushup(son);
now=son;
}
void insert(Node *&now,int x){
if(!now){
now=new Node(x);
return ;
}
if(now->num==x){now->size+=1;now->tot+=1;return;}
int wh=now->num<x;
insert(now->ch[wh],x);
pushup(now);
if(now->ch[wh]->key<now->key) rot(now,wh);
}
void del(Node *&now,int x){
if(now->num==x){
if(now->tot>1){now->size-=1;now->tot-=1;return;}
if(!now->ch[0]&&!now->ch[1]){delete now;now=NULL;}
else if(!now->ch[0]){
Node *t=now;
now=now->ch[1];
delete t; t=NULL;
}
else if(!now->ch[1]){
Node *t=now;
now=now->ch[0];
delete t; t=NULL;
}
else{
int wh=now->ch[0]->key>now->ch[1]->key;
rot(now,wh); del(now,x);
}
}
else{
if(now->num>x)del(now->ch[0],x);
else del(now->ch[1],x);
}
if(now) pushup(now);
}
int Rank(int x){
int ans=1; Node *now=root;
while(now){
if(now->num<x){
ans+=size(now->ch[0])+now->tot;
now=now->ch[1];
}
else if(now->num==x){ans+=size(now->ch[0]);break;}
else now=now->ch[0];
}
return ans;
}
int kth(int x){
Node *now=root; int all=x;
while(now){
if(size(now->ch[0])>=all) {now=now->ch[0];continue;}
all-=size(now->ch[0]);
if(now->tot>=all) return now->num;
all-=now->tot;
now=now->ch[1];
}
}
int pre(int x){return kth(Rank(x)-1);}
int next(int x){return kth(Rank(x+1));}
int main()
{
int n,opt,x; srand(time(NULL));
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&opt,&x);
switch(opt){
case 1: insert(root,x); break;
case 2: del(root,x); break;
case 3: printf("%d
",Rank(x)); break;
case 4: printf("%d
",kth(x)); break;
case 5: printf("%d
",pre(x)); break;
case 6: printf("%d
",next(x)); break;
}
}
}
无旋TREAP
using namespace std;
struct Treap{
Treap *ch[2];
int key,val,size;
Treap(int x){
size=1;val=x;key=rand();
ch[0]=ch[1]=NULL;
}
inline void pushup(){size=1+size(ch[0])+size(ch[1]);}
}*root;
Treap *merge(Treap *a,Treap *b){
if(!a)return b;
if(!b)return a;
if(a->key < b->key){
a->ch[1]=merge(a->ch[1],b);
a->pushup(); return a;
}
else{
b->ch[0]=merge(a,b->ch[0]);
b->pushup(); return b;
}
}
tp split(Treap *x,int k){
if(x==NULL)return tp(NULL,NULL);
tp y;
if(size(x->ch[0])>=k){
y=split(x->ch[0],k);
x->ch[0]=y.second;
x->pushup();
y.second=x;
}
else{
y=split(x->ch[1],k-size(x->ch[0])-1);
x->ch[1]=y.first;
x->pushup();y.first=x;
}
return y;
}
int getrank(Treap *x,int k){
if(x==NULL)return 0;
if(x->val>=k)
return getrank(x->ch[0],k);
else return getrank(x->ch[1],k)+size(x->ch[0])+1;
}
int getkth(int k){
tp x=split(root,k-1);
tp y=split(x.second,1);
Treap *ans=y.first;
root=merge(x.first,merge(ans,y.second));
return ans!=NULL?ans->val:0;
}
void insert(int x){
int k=getrank(root,x);
tp y=split(root,k);
Treap *rt=new Treap(x);
root=merge(merge(y.first,rt),y.second);
}
void delet(int x){
int k=getrank(root,x);
tp y=split(root,k);
tp z=split(y.second,1);
root=merge(y.first,z.second);
}
void print(Treap *x){
printf("%d %d
",x->key,x->val);
if(x->ch[0])print(x->ch[0]);
if(x->ch[1])print(x->ch[1]);
}
int main(){
int m; //srand(time(NULL));
scanf("%d",&m);
for(int i=1,opt,x;i<=m;i++){
scanf("%d%d",&opt,&x);
if(opt==1)insert(x);
if(opt==2)delet(x);
if(opt==3)printf("%d
",getrank(root,x)+1);
if(opt==4)printf("%d
",getkth(x));
if(opt==5)printf("%d
",getkth(getrank(root,x)));
if(opt==6)printf("%d
",getkth(getrank(root,x+1)+1));
if(opt==7)print(root);
}
return 0;
}