无旋Treap
#include <cstdio> #include <algorithm> #include <cstring> #include <ctime> #include <cstdlib> using namespace std; const int maxn=100100,inf=0x7fffffff; struct Treap { Treap* ch[2]; int key,val,size; Treap(int v){size=1,val=v,key=rand();ch[0]=ch[1]=NULL;} inline void tain() {size=1+(ch[0]?ch[0]->size:0)+(ch[1]?ch[1]->size:0);} }*root; typedef pair<Treap*,Treap*> D; inline int size(Treap *o){return o?o->size:0;} 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->tain(); return a; } else { b->ch[0]=Merge(a,b->ch[0]); b->tain(); return b; } } D Split(Treap *o,int k) { if(!o)return D(NULL,NULL); D y; if(size(o->ch[0])>=k) { y=Split(o->ch[0],k); o->ch[0]=y.second; o->tain(); y.second=o; } else { y=Split(o->ch[1],k-size(o->ch[0])-1); o->ch[1]=y.first; o->tain(); y.first=o; } return y; } int Getkth(Treap *o,int v) { if(o==NULL)return 0; return(o->val>=v)?Getkth(o->ch[0],v):Getkth(o->ch[1],v)+size(o->ch[0])+1; } inline int Findkth(int k) { D x=Split(root,k-1); D y=Split(x.second,1); Treap *ans=y.first; root=Merge(Merge(x.first,ans),y.second); return ans!=NULL?ans->val:0; } inline void Insert(int v) { int k=Getkth(root,v); D x=Split(root,k); Treap *o=new Treap(v); root=Merge(Merge(x.first,o),x.second); } void Delete(int v) { int k=Getkth(root,v); D x=Split(root,k); D y=Split(x.second,1); root=Merge(x.first,y.second); } int main() { int m,opt,x;scanf("%d",&m); while(m--) { scanf("%d%d",&opt,&x); switch(opt) { case 1:Insert(x);break; case 2:Delete(x);break; case 3:printf("%d ",Getkth(root,x)+1);break; case 4:printf("%d ",Findkth(x));break; case 5:printf("%d ",Findkth(Getkth(root,x)));break; case 6:printf("%d ",Findkth(Getkth(root,x+1)+1));break; } } }
Splay
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int N=1e7+5; int fa[N],cnt[N],son[N][3],size[N],key[N],type,root; int n; void clear(int x) { fa[x]=cnt[x]=son[x][0]=son[x][1]=size[x]=key[x]=0; } bool judge(int x) { return son[fa[x]][1]==x; } void up(int x) { if(x) { size[x]=cnt[x]; if(son[x][0])size[x]+=size[son[x][0]]; if(son[x][1])size[x]+=size[son[x][1]]; } } void rotate(int x) { int old=fa[x],oldf=fa[old],lr=judge(x); son[old][lr]=son[x][lr^1]; fa[son[old][lr]]=old; son[x][lr^1]=old; fa[old]=x; fa[x]=oldf; if(oldf)son[oldf][son[oldf][1]==old]=x; up(old);up(x); } void splay(int x) { for(int f;f=fa[x];rotate(x)) if(fa[f])rotate(judge(x)==judge(f)?f:x); root=x; } void ins(int x) { if(!root) { type++; key[type]=x; root=type; cnt[type]=size[type]=1; fa[type]=son[type][0]=son[type][1]=0; return ; } int now=root,f=0; while(1) { if(x==key[now]) { cnt[now]++; up(now); up(f); splay(now); return ; } f=now;now=son[now][key[now]<x]; if(!now) { type++; size[type]=cnt[type]=1; son[type][0]=son[type][1]=0; son[f][x>key[f]]=type; fa[type]=f; key[type]=x; up(f);splay(type); return ; } } } int getrank(int x) { int now=root,ans=0; while(1) { if(x<key[now])now=son[now][0]; else { ans+=size[son[now][0]]; if(x==key[now]) { splay(now); return ans+1; } ans+=cnt[now]; now=son[now][1]; } } } int getnum(int x) { int now=root; while(1) { if(son[now][0]&&x<=size[son[now][0]])now=son[now][0]; else { int tmp=size[son[now][0]]+cnt[now]; if(x<=tmp) return key[now]; x-=tmp;now=son[now][1]; } } } int pre() { int now=son[root][0]; while(son[now][1])now=son[now][1]; return now; } int nxt() { int now=son[root][1]; while(son[now][0])now=son[now][0]; return now; } void del(int x) { getrank(x); if(cnt[root]>1) { cnt[root]--; up(root); return ; } if(!son[root][0]&&(!son[root][1])) { clear(root); root=0; return ; } if(!son[root][0]) { int old=root; root=son[root][1]; fa[root]=0; clear(old); return ; } else if(!son[root][1]) { int old=root; root=son[root][0]; fa[root]=0; clear(old); return ; } int old=root,L=pre(); splay(L); son[root][1]=son[old][1]; fa[son[old][1]]=root; clear(old); up(root); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int op,val; scanf("%d%d",&op,&val); switch(op) { case 1:ins(val);break; case 2:del(val);break; case 3:printf("%d ",getrank(val));break; case 4:printf("%d ",getnum(val));break; case 5:ins(val);printf("%d ",key[pre()]);del(val);break; case 6:ins(val);printf("%d ",key[nxt()]);del(val);break; } } return 0; }
UPD:2019.8.4 Scapegoat Tree
UPD again:改完还是有错。感谢luogu网友@喝酸奶不舔盖 的提醒，之前更新祖先cnt相当于只改了它父亲而不是它的所有祖先。已修正。
UPD:之前放上来的板子有错。对于之前参考过这个代码的大佬们深感抱歉。
一共两处错误：
1.插入完之后没有找到深度最小的节点拍平，而是判一个坏点就拍平重建一次(这不sb吗)
解决：搞了一个指向指针地址的指针，回溯时每遇到一个坏点就更新目前深度最小坏点的信息，回溯完毕后只重建一次。
2.子树重建后坏点已删除，但它的祖先的cnt(不论好坏的点的总个数)并没有更新。其实没什么关系，但改了总比不改好(听学长的话.jpg)
解决：插入回溯时判断一下即可。
#include<cstdio> #include<iostream> #include<cstring> #include<vector> using namespace std; const double al=0.7; struct node { node *l,*r; int val,size,cnt; bool del; bool bad() { return l->cnt>al*cnt+5||r->cnt>al*cnt+5; } void up() { size=!del+l->size+r->size; cnt=1+l->cnt+r->cnt; } }; node *null,**badtag; void dfs(node *k,vector<node*> &v) { if(k==null)return ; dfs(k->l,v); if(!k->del)v.push_back(k); dfs(k->r,v); if(k->del)delete k; } node *build(vector<node*> &v,int l,int r) { if(l>=r)return null; int mid=l+r>>1; node *k=v[mid]; k->l=build(v,l,mid); k->r=build(v,mid+1,r); k->up(); return k; } void rebuild(node* &k) { vector<node*> v; dfs(k,v); k=build(v,0,v.size()); } void insert(int x,node* &k) { if(k==null) { k=new node; k->l=k->r=null; k->del=0; k->size=k->cnt=1; k->val=x; return ; } else { ++k->size;++k->cnt; if(x>=k->val)insert(x,k->r); else insert(x,k->l); if(k->bad())badtag=&k; else if(badtag!=&null) k->cnt-=(*badtag)->cnt-(*badtag)->size; } } void ins(int x,node* &k) { badtag=&null; insert(x,k); if(badtag!=&null)rebuild(*badtag); } int getrk(node *now,int x) { int ans=1; while(now!=null) { if(now->val>=x)now=now->l; else { ans+=now->l->size+!now->del; now=now->r; } } return ans; } int kth(node *now,int x) { while(now!=null) { if(!now->del&&now->l->size+1==x) return now->val; if(now->l->size>=x)now=now->l; else { x-=now->l->size+!now->del; now=now->r; } } } void erase(node *k,int rk) { if(!k->del&&rk==k->l->size+1) { k->del=1; --k->size; return ; } --k->size; if(rk<=k->l->size+!k->del)erase(k->l,rk); else erase(k->r,rk-k->l->size-!k->del); } node *root;int n; int main() { null=new node; root=null; scanf("%d",&n); while(n--) { int op,x; scanf("%d%d",&op,&x); switch(op) { case 1:ins(x,root);break; case 2:erase(root,getrk(root,x));break; case 3:printf("%d ",getrk(root,x));break; case 4:printf("%d ",kth(root,x));break; case 5:printf("%d ",kth(root,getrk(root,x)-1));break; case 6:printf("%d ",kth(root,getrk(root,x+1)));break; } } return 0; }
Splay区间翻转
namespace Splay
{
int fa[N],son[N][3],size[N],key[N],v[N],type,root;
inline bool judge(int x){return son[fa[x]][1]==x;}
inline void up(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;}
inline void down(int x)
{
if(x&&v[x])
{
v[son[x][0]]^=1;v[son[x][1]]^=1;
swap(son[x][0],son[x][1]);v[x]=0;
}
}
inline void rotate(int x)
{
int old=fa[x],oldf=fa[old],lr=judge(x);
down(old);down(x);
son[old][lr]=son[x][lr^1];
fa[son[old][lr]]=old;
son[x][lr^1]=old;fa[old]=x;
fa[x]=oldf;
if(oldf)son[oldf][son[oldf][1]==old]=x;
up(old);up(x);
}
inline void splay(int x,int goal)
{
for(int f;(f=fa[x])!=goal;rotate(x))
if(fa[f]!=goal)
rotate(judge(x)==judge(f)?f:x);
if(!goal)root=x;
}
int build(int f,int l,int r)
{
if(l>r)return 0;
int mid=l+r>>1,x=++type;
key[x]=a[mid];fa[x]=f;
v[x]=0;
son[x][0]=build(x,l,mid-1);
son[x][1]=build(x,mid+1,r);
up(x);
return x;
}
inline int getrank(int x)
{
int now=root;
while(1)
{
down(now);
if(x<=size[son[now][0]])now=son[now][0];
else
{
x-=size[son[now][0]]+1;
if(!x)return now;
now=son[now][1];
}
}
}
inline void rev(int l,int r)
{
l=getrank(l),r=getrank(r+2);
splay(l,0);splay(r,l);
down(root);
v[son[son[root][1]][0]]^=1;
}
void print(int now)
{
down(now);
if(son[now][0])print(son[now][0]);
if(key[now]!=-inf&&key[now]!=inf)b[++tot]=key[now];
if(key[son[now][1]])print(son[now][1]);
}
}