[BZOJ]3224: Tyvj 1728 普通平衡树

2019-11-08 18:43:31

字体：大中小

来源：转载

供稿：网友

平衡树的模板题。 Treap：

#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;#define C (c=getchar())inline void read(int &a){ a=0;static char c; int f=1; while(C<'0'||c>'9') c=='-'?f=-1:0; while(c>='0'&&c<='9') a=a*10+c-'0',C; a*=f; return ;}int n,x,y,sum;struct Treap{ int root,tnt,key[100006],PRiority[100006], childs[100006][3],cnt[100006],size[100006]; Treap() { root=0; tnt=1; priority[0]=2147483647; size[0]=0; } void maintain(int x) { size[x]=size[childs[x][0]]+size[childs[x][1]]+cnt[x]; return ; } void rotate(int &x,int t) { int y=childs[x][t]; childs[x][t]=childs[y][t^1]; childs[y][t^1]=x; maintain(x); maintain(y); x=y; return ; } void insert(int &x,int v) { if(x) { if(key[x]==v) cnt[x]++; else { int t=key[x]<v; insert(childs[x][t],v); if(priority[childs[x][t]]<priority[x]) rotate(x,t); } } else { x=tnt++; key[x]=v; cnt[x]=1; priority[x]=rand(); childs[x][0]=childs[x][1]=0; } maintain(x); } void erase(int &x,int v) { if(x==0) return ; if(key[x]==v) { if(cnt[x]>1) --cnt[x]; else { if(childs[x][0]==0&&childs[x][1]==0) { x=0; return ; } int t=priority[childs[x][0]]>priority[childs[x][1]]; rotate(x,t); erase(x,v); } } else erase(childs[x][key[x]<v],v); maintain(x); return ; } int geth(int x,int v) { if(x==0) return 0; if(v<=size[childs[x][0]]) return geth(childs[x][0],v); v-=size[childs[x][0]]+cnt[x]; if(v<=0) return key[x]; return geth(childs[x][1],v); } int getth(int x,int v) { if(x==0) return 0; if(v<key[x]) return getth(childs[x][0],v); if(v==key[x]) return size[childs[x][0]]+1; return size[childs[x][0]]+cnt[x]+getth(childs[x][1],v); } void prev(int x,int v) { if(x==0) return ; if(key[x]<v) { sum=key[x]; prev(childs[x][1],v); } else prev(childs[x][0],v); return ; } void next(int x,int v) { if(x==0) return ; if(key[x]>v) { sum=key[x]; next(childs[x][0],v); } else next(childs[x][1],v); return ; }}ClroVer;int main(void){ register int i; srand(1); read(n); for (i=1;i<=n;++i) { read(x),read(y); switch(x) { case 1:ClroVer.insert(ClroVer.root,y);break; case 2:ClroVer.erase(ClroVer.root,y);break; case 3:printf("%d/n",ClroVer.getth(ClroVer.root,y));break; case 4:printf("%d/n",ClroVer.geth(ClroVer.root,y));break; case 5:ClroVer.prev(ClroVer.root,y);printf("%d/n",sum);break; default:ClroVer.next(ClroVer.root,y);printf("%d/n",sum);break; } } return 0;}

Splay：

#include <cstdio>using namespace std;#define C (c=getchar())inline void read(int &a){ a=0;static char c; int f=1; while(C<'0'||c>'9') c=='-'?f=-1:0; while(c>='0'&&c<='9') a=a*10+c-'0',C; a*=f; return ;}int n,x,y;struct Splay{ int sz,root,f[100003],ch[100003][2],size[100003],cnt[100003],key[100003]; int get(int x) { return ch[f[x]][1]==x; } void maintain(int x) { size[x]=cnt[x]; size[x]+=size[ch[x][0]]; size[x]+=size[ch[x][1]]; return ; } void rotate(int x) { int fa=f[x],fafa=f[fa],which=get(x); ch[fa][which]=ch[x][1^which]; f[ch[fa][which]]=fa; f[fa]=x;ch[x][1^which]=fa; f[x]=fafa; if(fafa) ch[fafa][ch[fafa][1]==fa]=x; maintain(x),maintain(fa); return ; } void splay(int x) { for (int fa;fa=f[x];rotate(x)) if(f[fa]) rotate((get(fa)==get(x))?fa:x); root=x; return ; } void insert(int x) { int now=root,fa=0; while(1) { if(key[now]==x) { ++cnt[now];maintain(now);maintain(fa); splay(now);return ; } if(now==0) { ++sz,cnt[sz]=size[sz]=1; ch[sz][0]=ch[sz][1]=0;f[sz]=fa,key[sz]=x; if(root==0) root=sz; if(fa!=0) ch[fa][key[fa]<x]=sz; maintain(sz),maintain(fa),splay(sz); return ; } fa=now,now=ch[now][x>key[now]]; } } int find(int x) { int ans=0,now=root; while(1) { if(now==0) return -1; if(x<key[now]) now=ch[now][0]; else { if(ch[now][0]) ans+=size[ch[now][0]]; if(key[now]==x) { splay(now); return ans+1; } ans+=cnt[now]; now=ch[now][1]; } } } int findx(int x) { int now=root; while(1) { if(now==0) return -1; if(ch[now][0]&&x<=size[ch[now][0]]) now=ch[now][0]; else { x-=size[ch[now][0]],x-=cnt[now]; if(x<=0) return key[now]; else now=ch[now][1]; } } } int pre() { int now=ch[root][0]; while(ch[now][1]) now=ch[now][1]; return now; } int nex() { int now=ch[root][1]; while(ch[now][0]) now=ch[now][0]; return now; } void erase(int x) { if(find(x)==-1) return ; if(cnt[root]>1) { --cnt[root]; maintain(root); return ; } if(ch[root][0]*ch[root][1]==0) { root=ch[root][0]+ch[root][1]; f[root]=0; return ; } int lb=pre(),old=root; splay(lb); if(f[ch[old][1]]) f[ch[old][1]]=root,ch[root][1]=ch[old][1]; maintain(root); return ; }}ClroVer;int main(void){ register int i; read(n); for (i=1;i<=n;++i) { read(x),read(y); switch(x) { case 1:ClroVer.insert(y);break; case 2:ClroVer.erase(y);break; case 3:printf("%d/n",ClroVer.find(y));break; case 4:printf("%d/n",ClroVer.findx(y));break; case 5:ClroVer.insert(y),printf("%d/n",ClroVer.key[ClroVer.pre()]);ClroVer.erase(y);break; default:ClroVer.insert(y),printf("%d/n",ClroVer.key[ClroVer.nex()]);ClroVer.erase(y);break; } } return 0;}

上一篇：嵌入式采集温度DS18B20-platform驱动

下一篇：LintCode 9 Fizz Buzz 问题