先吐槽一下，要找塊好模闆真不容易，畢竟大家都有各自的代碼風格，強迫自己去看非自己風格的代碼真是痛苦，是以在網上添加一種類型的模闆
最近才發現這題A了三遍，分别是以三種平衡樹的模闆題A的，是以稍微彙總一下，讓後來者有個類型的模闆可以依靠
相信看模闆的人都看過題解了，是以這裡就不寫題解了 本來就是模闆題，哪來的題解
如果有剛學平衡樹的，奉勸一句
splay好好學，SBT慢慢學，treap仔細學
splay s p l a y 版：
#include<bits/stdc++.h>
using namespace std;
#define update(x) tr[x].size=tr[tr[x].ch[0]].size+tr[tr[x].ch[1]].size+tr[x].cnt
#define cl(x) memset(x,0,sizeof(x))
#define cl1(x) memset(x,-1,sizeof(x))
#define rg register
#define oo 0x3f3f3f3f
template <typename _Tp> inline void read(_Tp&x){char c11=getchar();x=;bool booo=;
while(c11!='-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),booo=;
while(isdigit(c11)){x=x*+c11-'0';c11=getchar();}if(booo)x=-x;return ;
}
const int N=;
struct node{int size,f,ch[],val,cnt;}tr[N];
int root,sz;
inline int nxt(int,int);
inline void find(int);
inline void insert(int);
inline void del(int);
inline int K_th(int);
inline void rotate(int x){
int fa=tr[x].f;
int grand=tr[fa].f;
int le=(tr[fa].ch[]==x);
tr[grand].ch[tr[grand].ch[]==fa]=x;
tr[x].f=grand;
tr[fa].ch[le]=tr[x].ch[le^];
tr[tr[x].ch[le^]].f=fa;
tr[x].ch[le^]=fa;
tr[fa].f=x;
update(fa);update(x);
return ;
}
void splay(int x,int target){
for(rg int fa;(fa=f[x])!=target;rotate(x))
if(f[f[x]]!=target)
rotate(blood(x)==blood(f[x])?f[x]:x);
if(!target)root=x;
return ;
}
int main(){
insert(-oo);insert(+oo);
rg int m,opt,A;read(m);
while(m--){
read(opt);read(A);
switch(opt){
case :
insert(A);
break;
case :
del(A);
break;
case :
find(A);
printf("%d\n",tr[tr[root].ch[]].size);
break;
case :
printf("%d\n",K_th(A+));
break;
case :
printf("%d\n",tr[nxt(A,)].val);
break;
case :
printf("%d\n",tr[nxt(A,)].val);
break;
default:
puts("ERROR");
return ;
}
}
return ;
}
inline int K_th(int x){
int now=root;
if(tr[now].size<x)return -;
while("KB is too powerful"){
if(x>tr[tr[now].ch[]].size+tr[now].cnt){
x-=tr[tr[now].ch[]].size+tr[now].cnt;
now=tr[now].ch[];
}
else
if(x<=tr[tr[now].ch[]].size)
now=tr[now].ch[];
else
return tr[now].val;
}
return -;
}
inline void del(int x){
int fr=nxt(x,),Ba=nxt(x,);
splay(fr,);splay(Ba,fr);
if(tr[tr[Ba].ch[]].cnt>){
--tr[tr[Ba].ch[]].cnt;
splay(tr[Ba].ch[],);
}
else
tr[Ba].ch[]=;
return ;
}
inline void insert(int x){
int now=root,f=;
while(now&&tr[now].val!=x){
f=now;
now=tr[now].ch[x>tr[now].val];
}
if(now)++tr[now].cnt;
else{
now=++sz;
if(f)tr[f].ch[x>tr[f].val]=now;
tr[now].ch[]=tr[now].ch[]=;
tr[now].f=f,tr[now].val=x;
tr[now].cnt=;tr[now].size=;
}
splay(now,);
return ;
}
inline int nxt(int x,int leaf){
find(x);
int now=root;
if(leaf&&tr[now].val>x)return now;
if(!leaf&&tr[now].val<x)return now;
now=tr[now].ch[leaf];
while(tr[now].ch[leaf^])now=tr[now].ch[leaf^];
return now;
}
inline void find(int x){
if(!root)return ;
int now=root;
while(tr[now].ch[x>tr[now].val]&&x!=tr[now].val)now=tr[now].ch[x>tr[now].val];
splay(now,);
return ;
}
treap t r e a p 版：
//bzoj3224
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define update(x) size[now]=size[ch[now][0]]+size[ch[now][1]]+tot[now];
template <typename _Tp> inline void read(_Tp&x){
char c11=getchar();x=;bool booo=;
while(c11!='-'&&!isdigit(c11))c11=getchar();if(c11=='-'){c11=getchar();booo=;}
while(isdigit(c11)){x=x*+c11-'0';c11=getchar();}if(booo)x=-x;return ;
}
const int N=;
int ch[N][],data[N],rnd[N],tot[N],size[N];
int n,root,ans,sz;
inline void lturn(int &now){
int child=ch[now][];ch[now][]=ch[child][];ch[child][]=now;
size[child]=size[now];update(now);now=child;
return ;
}
inline void rturn(int &now){
int child=ch[now][];ch[now][]=ch[child][];ch[child][]=now;
size[child]=size[now];update(now);now=child;
return ;
}
void ins(int &now,int x){
if(!now){
now=++sz;
size[now]=tot[now]=;
data[now]=x;rnd[now]=rand();
return ;
}
++size[now];
if(data[now]==x){++tot[now];return ;}
if(data[now]<x){
ins(ch[now][],x);
if(rnd[ch[now][]]<rnd[now])lturn(now);
}
else{
ins(ch[now][],x);
if(rnd[ch[now][]]<rnd[now])rturn(now);
}
return ;
}
void del(int &now,int x){
if(!now)return ;
if(data[now]==x){
if(tot[now]>){--tot[now],--size[now];return ;}
if(!(ch[now][]*ch[now][])){now=ch[now][]+ch[now][];return ;}
if(rnd[ch[now][]]<rnd[ch[now][]])
rturn(now),del(now,x);
else
lturn(now),del(now,x);
return ;
}
--size[now];
if(data[now]<x)
del(ch[now][],x);
else
del(ch[now][],x);
return ;
}
int get_rank(int x){
int now=root,basic=;
while(){
if(!now)break;
if(data[now]==x){basic+=size[ch[now][]]+;break;}
if(x<data[now])now=ch[now][];
else basic+=size[ch[now][]]+tot[now],now=ch[now][];
}
return basic;
}
int get_num(int x){
int now=root;
while(){
if(!now)return ;
if(x<=size[ch[now][]]){
now=ch[now][];
continue;
}
if(x>size[ch[now][]]+tot[now]){
x-=size[ch[now][]]+tot[now];
now=ch[now][];
continue;
}
else
return data[now];
}
}
void front(int x){
int now=root;
while(){
if(!now)return ;
if(data[now]<x)
ans=now,now=ch[now][];
else
now=ch[now][];
}
return ;
}
void back(int x){
int now=root;
while(){
if(!now)return ;
if(x<data[now])
ans=now,now=ch[now][];
else
now=ch[now][];
}
return ;
}
int main(){
freopen("in","r",stdin);
// srand(time(0));
read(n);
int opt,x;
while(n--){
read(opt);read(x);
switch(opt){
case :ins(root,x);break;
case :del(root,x);break;
case :printf("%d\n",get_rank(x));break;
case :printf("%d\n",get_num(x));break;
case :ans=;front(x);printf("%d\n",data[ans]);break;
case :ans=;back(x);printf("%d\n",data[ans]);break;
default :puts("ERROR IN INPUT");return ;
}
}
return ;
}
SBT S B T 版：
#include<bits/stdc++.h>
using namespace std;
#define cl(x) memset(x,0,sizeof(x))
#define rg register
template <typename _Tp> inline void read(_Tp&x){
char c11=getchar();x=;bool booo=;
while(c11!='-'&&!isdigit(c11))c11=getchar();if(c11=='-'){c11=getchar();booo=;}
while(isdigit(c11)){x=x*+c11-'0';c11=getchar();}if(booo)x=-x;return ;
}
const int N=;
struct sbt{
int rt,sz;
int data[N],ch[N][],size[N];
void clear(){
rt=sz=;
cl(data),cl(ch),cl(size);
}
void zig(int &p){
int k=ch[p][];
ch[p][]=ch[k][];
ch[k][]=p;
size[k]=size[p];
size[p]=size[ch[p][]]+size[ch[p][]]+;
p=k;
}
void zag(int &p){
int k=ch[p][];
ch[p][]=ch[k][];
ch[k][]=p;
size[k]=size[p];
size[p]=size[ch[p][]]+size[ch[p][]]+;
p=k;
}
void maintain(int &p,bool flag){
#define L ch[p][0]
#define R ch[p][1]
#define LL ch[ch[p][0]][0]
#define LR ch[ch[p][0]][1]
#define RL ch[ch[p][1]][0]
#define RR ch[ch[p][1]][1]
if(!flag)
if(size[LL]>size[R])zag(p);
else
if(size[LR]>size[R]){zig(L);zag(p);}
else return ;
else
if(size[RR]>size[L])zig(p);
else
if(size[RL]>size[L]){zag(R);zig(p);}
else return ;
maintain(L,);
maintain(R,);
maintain(p,);
maintain(p,);
return ;
}
void ins(int &p,int x){
if(!p){
p=++sz;data[sz]=x,size[sz]=;
return ;
}
++size[p];
ins(ch[p][data[p]<=x],x);
maintain(p,x>=data[p]);
}
int erase(int &p,int x){
--size[p];int tmp;
if(x==data[p]||(x<data[p]&&!ch[p][])||(data[p]<x&&!ch[p][])){
tmp=data[p];
if(!ch[p][]||!ch[p][])p=ch[p][]+ch[p][];
else data[p]=erase(ch[p][],data[p]+);
return tmp;
}
tmp=erase(ch[p][data[p]<=x],x);
return tmp;
}
int rank(int &p,int x){
if(!p)return ;int tmp=;
if(x<=data[p])tmp=rank(ch[p][],x);
else tmp=size[ch[p][]]++rank(ch[p][],x);
return tmp;
}
int num(int &p,int x){
if(x==size[ch[p][]]+)return data[p];
if(x<=size[ch[p][]])return num(ch[p][],x);
return num(ch[p][],x--size[ch[p][]]);
}
int front(int &p,int x){
if(!p)return x;int tmp;
if(x<=data[p])tmp=front(ch[p][],x);
else{tmp=front(ch[p][],x);if(tmp==x)tmp=data[p];}
return tmp;
}
int back(int &p,int x){
if(!p)return x;int tmp;
if(data[p]<=x)tmp=back(ch[p][],x);
else{tmp=back(ch[p][],x);if(tmp==x)tmp=data[p];}
return tmp;
}
}T;
int main(){
freopen("in","r",stdin);
int m;read(m);
T.clear();
int &rt=T.rt=;
while(m--){
int opt,x;
read(opt);read(x);
switch(opt){
case :T.ins(rt,x);break;
case :T.erase(rt,x);break;
case :printf("%d\n",T.rank(rt,x));break;
case :printf("%d\n",T.num(rt,x));break;
case :printf("%d\n",T.front(rt,x));break;
case :printf("%d\n",T.back(rt,x));break;
}
}
return ;
}
![通關PAT留念[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)