【bzoj 3224】一般バランスツリーTreap
バランスツリーの基本操作(←今しかできないSB).直接Treapを裸にすればいいです(なぜ黄先輩に似ているのか聞かないでください.私のデータ構造は彼のテンプレートによって来たからです).
MACコードは以下の通りである.
by lych
2016.3.16
MACコードは以下の通りである.
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define N 100005
using namespace std;
int n,trtot,rt,ans,c[N][2],sz[N],sum[N],rd[N],val[N];
int read(){
int x=0,fu=1; char ch=getchar();
while (ch<'0' || ch>'9'){ if (ch=='-') fu=-1; ch=getchar(); }
while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
return x*fu;
}
void rotate(int &k,int l){
int t=c[k][l]; c[k][l]=c[t][l^1]; c[t][l^1]=k;
sz[t]=sz[k]; sz[k]=sz[c[k][0]]+sz[c[k][1]]+sum[k]; k=t;
}
void ins(int &k,int x){
if (!k){
k=++trtot; sz[k]=sum[k]=1;
val[k]=x; rd[k]=rand(); return;
}
sz[k]++;
if (x==val[k]) sum[k]++; else
if (x<val[k]){
ins(c[k][0],x); if (rd[c[k][0]]<rd[k]) rotate(k,0);
} else{
ins(c[k][1],x); if (rd[c[k][1]]<rd[k]) rotate(k,1);
}
}
void del(int &k,int x){
if (x==val[k]){
if (sum[k]>1){ sz[k]--; sum[k]--; return; }
if (!c[k][0] || !c[k][1]) k=c[k][0]+c[k][1]; else
if (rd[c[k][0]]<rd[c[k][1]]){ rotate(k,0); del(k,x); }
else{ rotate(k,1); del(k,x); }
} else{
if (x<val[k]) del(c[k][0],x); else del(c[k][1],x);
sz[k]--;
}
}
int getrnk(int k,int x){
if (x==val[k]) return sz[c[k][0]]+1; else
if (x<val[k]) return getrnk(c[k][0],x); else
return sz[c[k][0]]+sum[k]+getrnk(c[k][1],x);
}
int find(int k,int rst){
if (rst<=sz[c[k][0]]) return find(c[k][0],rst); else
if (rst>sz[c[k][0]]+sum[k]) return find(c[k][1],rst-sz[c[k][0]]-sum[k]);
else return val[k];
}
void getpre(int k,int x){
if (!k) return;
if (val[k]<x){ ans=k; getpre(c[k][1],x); } else getpre(c[k][0],x);
}
void getnxt(int k,int x){
if (!k) return;
if (val[k]>x){ ans=k; getnxt(c[k][0],x); } else getnxt(c[k][1],x);
}
int main(){
srand(20160316); int cas=read(),k,x;
while (cas--){
k=read(); x=read();
if (k==1) ins(rt,x); else if (k==2) del(rt,x); else
if (k==3) printf("%d
",getrnk(rt,x)); else
if (k==4) printf("%d
",find(rt,x)); else{
ans=0; if (k==5) getpre(rt,x); else getnxt(rt,x);
printf("%d
",val[ans]);
}
}
return 0;
}
by lych
2016.3.16