AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3224
借此题来练习平衡树的模板。（以下数据均为bzoj亲测数据）
【Treap】
Memory：3762kb
Time：248ms
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> using namespace std; #define FILE "read" #define MAXN 100005 int n,len,root,ans; namespace INIT{ char buf[1<<15],*fs,*ft; inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;} inline int read(){ int x=0,f=1; char ch=getc(); while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();} while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();} return x*f; } }using namespace INIT; namespace Treap_Tree{ struct node{int l,r,v,size,fix,w;}tr[MAXN]; void update(int k){tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w;} void rturn(int &k){int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;tr[t].size=tr[k].size;update(k);k=t;} void lturn(int &k){int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;tr[t].size=tr[k].size;update(k);k=t;} void insert(int &k,int x){ if(k==0){len++;k=len;tr[k].size=tr[k].w=1;tr[k].v=x;tr[k].fix=rand();return;} tr[k].size++; if(tr[k].v==x)tr[k].w++; else if(x>tr[k].v){insert(tr[k].r,x);if(tr[tr[k].r].fix<tr[k].fix)lturn(k);} else {insert(tr[k].l,x);if(tr[tr[k].l].fix<tr[k].fix)rturn(k);} } void del(int &k,int x){ if(k==0)return; if(tr[k].v==x){ if(tr[k].w>1){tr[k].w--;tr[k].size--;return;} if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r; else if(tr[tr[k].l].fix<tr[tr[k].r].fix)rturn(k),del(k,x); else lturn(k),del(k,x); } else if(x>tr[k].v)tr[k].size--,del(tr[k].r,x); else tr[k].size--,del(tr[k].l,x); } int rank(int k,int x){ if(k==0)return 0; if(tr[k].v==x)return tr[tr[k].l].size+1; else if(x>tr[k].v)return tr[tr[k].l].size+tr[k].w+rank(tr[k].r,x); else return rank(tr[k].l,x); } int Findkth(int k,int x){ if(k==0)return 0; if(x<=tr[tr[k].l].size)return Findkth(tr[k].l,x); else if(x>tr[tr[k].l].size+tr[k].w)return Findkth(tr[k].r,x-tr[tr[k].l].size-tr[k].w); else return tr[k].v; } void get_before(int k,int x){ if(k==0)return; if(tr[k].v<x){ans=k;get_before(tr[k].r,x);} else get_before(tr[k].l,x); } void get_behind(int k,int x){ if(k==0)return; if(tr[k].v>x){ans=k;get_behind(tr[k].l,x);} else get_behind(tr[k].r,x); } }using namespace Treap_Tree; int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); n=read(); int flag,x; for(int i=1;i<=n;i++){ flag=read(); x=read(); switch(flag){ case 1:insert(root,x);break; case 2:del(root,x);break; case 3:printf("%d\n",rank(root,x));break; case 4:printf("%d\n",Findkth(root,x));break; case 5:ans=0;get_before(root,x);printf("%d\n",tr[ans].v);break; case 6:ans=0;get_behind(root,x);printf("%d\n",tr[ans].v);break; } } return 0; } 【Splay】Memory:3668kb
Time:484ms
/************* Splay模板 by chty 2016.12.23 *************/ #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> using namespace std; #define FILE "phs" #define MAXN 100010 #define up(i,j,n) for(int i=j;i<=n;i++) #define dn(i,j,n) for(int i=j;i>=n;i--) #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) namespace INIT{ char buf[1<<15],*fs,*ft; inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;} inline int read(){ int x=0,f=1; char ch=getc(); while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();} while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();} return x*f; } }using namespace INIT; namespace Splay_Tree{ int root,cnt,v[MAXN],w[MAXN],size[MAXN],f[MAXN],son[MAXN][2]; bool get(int x) {return son[f[x]][1]==x;} void clear(int x) {son[x][0]=son[x][1]=v[x]=w[x]=f[x]=size[x]=0;} void updata(int x) {size[x]=size[son[x][0]]+size[son[x][1]]+w[x];} int before(){int now=son[root][0];while(son[now][1]) now=son[now][1];return now;} int behind(){int now=son[root][1];while(son[now][0]) now=son[now][0];return now;} void rotate(int x){ int y=f[x],z=f[y],which=get(x); son[y][which]=son[x][which^1]; f[son[y][which]]=y; f[y]=x; son[x][which^1]=y; f[x]=z; if(z) son[z][son[z][1]==y]=x; updata(y); updata(x); } void splay(int x){for(int fa;(fa=f[x]);rotate(x))if(f[fa])rotate((get(x)==get(fa)?fa:x));root=x;} void insert(int value){ int now=root,fa(0); if(!now) {root=++cnt;v[root]=value;size[root]=w[root]=1;return;} while(1){ if(value==v[now]) {w[now]++;splay(now);break;} fa=now; now=son[now][value>v[now]]; if(now==0){ now=++cnt;v[now]=value;size[now]=w[now]=1; f[now]=fa; son[fa][value>v[fa]]=now;splay(now); break; } } } int find_rank(int value){ int now=root,ans(0); while(1){ if(value<v[now]) now=son[now][0]; else{ ans+=size[son[now][0]]; if(value==v[now]) {splay(now); return ans+1;} ans+=w[now]; now=son[now][1]; } } } int find_Kth(int x){ int now=root; while(1){ if(son[now][0]&&x<=size[son[now][0]]) now=son[now][0]; else{ int temp=size[son[now][0]]+w[now]; if(x<=temp) return v[now]; x-=temp; now=son[now][1]; } } } void del(int value){ find_rank(value); if(w[root]>1) {w[root]--; size[root]--;} else if(son[root][0]+son[root][1]==0) clear(root),root=0; else if(!son[root][0]) {int last=root;root=son[root][1];f[root]=0;clear(last);} else if(!son[root][1]) {int last=root;root=son[root][0];f[root]=0;clear(last);} else{ int x=before(),last=root; splay(x); son[root][1]=son[last][1]; f[son[last][1]]=root; clear(last); updata(root); } } }using namespace Splay_Tree; int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); int n=read(); for(int i=1;i<=n;i++){ int flag=read(),x=read(); switch(flag){ case 1:insert(x);break; case 2:del(x);break; case 3:printf("%d\n",find_rank(x));break; case 4:printf("%d\n",find_Kth(x));break; case 5:insert(x);printf("%d\n",v[before()]);del(x);break; case 6:insert(x);printf("%d\n",v[behind()]);del(x);break; } } return 0; } 【替罪羊树】
Memory：3668kb
Time：180ms
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<ctime> #include<algorithm> using namespace std; #define INF 1000000000 #define FILE "read" int n,len,root,top,stack[100005]; namespace INIT{ char buf[1<<15],*fs,*ft; inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;} inline int read(){ int x=0,f=1; char ch=getc(); while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();} while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();} return x*f; } }using namespace INIT; namespace TiZuiYang_Tree{ const double chty=0.75; //平衡常数 struct node{int son[2],f,size,v;}tr[100005]; void init(){ len=2; root=1; tr[1].size=2; tr[1].v=-INF; tr[1].son[1]=2; tr[2].size=1; tr[2].v=INF; tr[2].f=1; } bool balance(int x) { double p=tr[x].size*chty; return p>=(double)tr[tr[x].son[0]].size&&p>=(double)tr[tr[x].son[1]].size; } void dfs(int x){//中序遍历 if(!x) return; dfs(tr[x].son[0]); stack[++top]=x; dfs(tr[x].son[1]); } int build(int l,int r){ if(l>r) return 0; int mid=(l+r)/2,x=stack[mid]; tr[tr[x].son[0]=build(l,mid-1)].f=x; tr[tr[x].son[1]=build(mid+1,r)].f=x; tr[x].size=tr[tr[x].son[0]].size+tr[tr[x].son[1]].size+1; return x; } void rebuild(int x){ top=0; dfs(x); int fa=tr[x].f,which=(tr[fa].son[1]==x); int sonroot=build(1,top); tr[tr[fa].son[which]=sonroot].f=fa; if(x==root) root=sonroot; } int find(int v){ int now=root; while(now){ if(v==tr[now].v) return now; else now=tr[now].son[v>tr[now].v]; } } void insert(int v){ int now=root,p=++len; tr[p].v=v; tr[p].size=1;//新开结点 while(1){ tr[now].size++; int which=(v>=tr[now].v);//表示p在当前根的哪个子树内 if(tr[now].son[which]) now=tr[now].son[which]; else {tr[tr[now].son[which]=p].f=now; break;} } int id=0; for(int i=p;i;i=tr[i].f) if(!balance(i)) id=i;//记录不平衡点 if(id) rebuild(id);//重构子树 } void del(int x){ if(tr[x].son[0]&&tr[x].son[1]){ int p=tr[x].son[0]; while(tr[p].son[1]) p=tr[p].son[1]; tr[x].v=tr[p].v; x=p; } int Son=(tr[x].son[0])?tr[x].son[0]:tr[x].son[1],which=(tr[tr[x].f].son[1]==x); tr[tr[tr[x].f].son[which]=Son].f=tr[x].f; for(int i=tr[x].f;i;i=tr[i].f) tr[i].size--; if(x==root) root=Son; } int rank(int v){ int now=root,ans=0; while(now){ if(tr[now].v<v) {ans+=tr[tr[now].son[0]].size+1; now=tr[now].son[1];} else now=tr[now].son[0]; } return ans; } int kth(int x){ int now=root; while(1){ if(tr[tr[now].son[0]].size==x-1) return now; else if(tr[tr[now].son[0]].size>=x) now=tr[now].son[0]; else x-=tr[tr[now].son[0]].size+1,now=tr[now].son[1]; } return now; } int before(int v){ int now=root,ans=-INF; while(now){ if(tr[now].v<v) ans=max(ans,tr[now].v),now=tr[now].son[1]; else now=tr[now].son[0]; } return ans; } int after(int v){ int now=root,ans=INF; while(now){ if(tr[now].v>v) ans=min(ans,tr[now].v),now=tr[now].son[0]; else now=tr[now].son[1]; } return ans; } }using namespace TiZuiYang_Tree; int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); init(); n=read(); for(int i=1;i<=n;i++){ int flag=read(),x=read(); if(flag==1) insert(x); if(flag==2) del(find(x)); if(flag==3) printf("%d\n",rank(x)); if(flag==4) printf("%d\n",tr[kth(x+1)].v); if(flag==5) printf("%d\n",before(x)); if(flag==6) printf("%d\n",after(x)); } return 0; }
