正文
可持久化Treap 赛前摸鱼笔记
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
1.基本结构
随机化工具
unsigned int SEED = 19260817; //+1s
inline int Rand(){
SEED=SEED*1103515245+12345;
return SEED/65536;
}
内部成员
struct Treap{
int son[MAXN][2],val[MAXN],fix[MAXN],size[MAXN];
int tot,root;
#define lc son[o][0]
#define rc son[o][1]
}
初始化与构造
void init(){
root=0;//用于判断是否为NULL
tot=1; //所以tot从1遍历
son[0][0]=son[0][1]=val[0]=fix[0]=size[0]=0;
}
int node(int v){
son[tot][0]=son[tot][1]=0;
size[tot]=1;
val[tot]=v; //权值
fix[tot]=Rand(); //附加权值
return tot++;
}
void pu(int o){
size[o]=1+size[lc]+size[rc];
}
2.核心操作
void split(int o,int pivot,int &a,int &b){
if(!o){
a=b=0;
return;
}else if(val[o]<=pivot){ //如果节点权值小于等于pivot
a=o; //o所有左子树放到左边的树
split(rc,pivot,rc,b); //遍历右儿子
}else{
b=o;
split(lc,pivot,a,lc);
}
pu(o);
}
整体而言,这个操作就是把一个Treap分裂为左Treap和右Treap并把根节点分别赋给a b,其中左Treap所有权值总是小于等于pivot,右Treap则大于
并且这个操作复杂度为\(O(logn)\),下面简略说一下过程
来个小实验
int son[MAXN][2],val[MAXN];
#define lc son[o][0]
#define rc son[o][1]
void split(int o,int pivot,int &a,int &b){
if(!o){
a=b=0;
return;
}else if(val[o]<=pivot){
a=o;
split(rc,pivot,rc,b);
}else{
b=o;
split(lc,pivot,a,lc);
}
}
int main(){
val[1]=3,val[2]=2,val[3]=7;
val[4]=1,val[5]=5,val[6]=8;
val[7]=4,val[8]=6;
son[1][0]=2,son[1][1]=3;
son[2][0]=4;
son[3][0]=5,son[3][1]=6;
son[5][0]=7,son[5][1]=8;
int a,b;
split(1,5,a,b);
cout<<a<<" "<<b<<endl;
cout<<son[5][1]<<endl;
}
对方不想说话,并掏出了...沾满灰尘的破板子
可以看出往左倾斜的方块放在a子树,往右倾斜的放在b子树,并且不断拼接就能分裂成完整的a和b
并且每一次操作就能把一半的子树摆好位置(随机fixed的情况下),所以整个操作流程就是\(O(logn)\)
一般使用还是按size划分比较好,提取区间简单轻松
void split(int o,int k,int &a,int &b){
if(!o){
a=b=0;
return;
}else if(k<=size[lc]){
b=o;
split(lc,k,a,lc);
pu(o);
}else{
a=o;
split(rc,k-size[lc]-1,rc,b);
pu(o);
}
}
int merge(int a,int b){ //保证val比较时a是左子树,b是右子树
if(!a) return b;
if(!b) return a;
if(fix[a]<fix[b]){
son[a][1]=merge(son[a][1],b);
pu(a);
return a; //a的左子树保留,(可能)更改右子树关系
}else{
son[b][0]=merge(a,son[b][0]);
pu(b);
return b;
}
}
merge是一个维护堆性质的过程,这个操作是十分的简单粗暴,再上一个小实验
int son[MAXN][2],fix[MAXN];
#define lc son[o][0]
#define rc son[o][1]
int merge(int a,int b){
if(!a)return a;if(!b)return b;
if(fix[a]<fix[b]){
son[a][1]=merge(son[a][1],b);
return a;
}else{
son[b][0]=merge(a,son[b][0]);
return b;
}
}
int main(){
fix[1]=10,fix[2]=20,fix[3]=30;
fix[4]=40,fix[5]=50,fix[6]=60;
fix[7]=80;
fix[8]=35,fix[9]=47,fix[10]=45;
fix[11]=75,fix[12]=65,fix[13]=55;
son[1][0]=2,son[1][1]=3;
son[2][0]=4;son[3][0]=5,son[3][1]=6;
son[4][0]=7;
son[8][0]=9,son[8][1]=10;
son[9][0]=11,son[9][1]=12;
son[10][1]=13;
merge(1,8);
for(int i=1;i<=12;i++){
cout<<i<<" "<<son[i][0]<<" "<<son[i][1]<<endl;
}
}
(这回画的更丑了)
可以看到其实还是一个分块再合并的过程,看着和斜堆很像,但更为暴力的是这家伙连左右交换都不做(当然它是有随机化buff加成可以为所欲为,而且还要维护val呢)
也就是说这个过程仅仅是通过维护一个堆的性质来合并而已,因为Rand()的存在令它依然是妥妥的\(O(logn)\)
按道理说想要降低常数那说还有一种策略就是把递归换成栈实现的迭代式,对频繁使用的核心操作而言应该是不小的提升,但递归写起来真方便..
3.区间操作
先来个最最简单插入/查询
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int MAXN = 1e5+11;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
typedef long long ll;
const ll MOD = 1e9+7;
unsigned int SEED = 17;
ll read(){
ll x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline int Rand(){
SEED=SEED*1103515245+12345;
return SEED/65536;
}
struct Treap{
int son[MAXN][2],root,tot;
int val[MAXN],fix[MAXN],size[MAXN];
#define lc son[o][0]
#define rc son[o][1]
void init(){
root=0;
son[0][0]=son[0][1]=0;
val[0]=fix[0]=size[0]=0;
tot=1;
}
int node(int v){
son[tot][0]=son[tot][1]=0;
val[tot]=v; fix[tot]=Rand();
size[tot]=1;
return tot++;
}
void pu(int o){
size[o]=size[lc]+size[rc]+1;
}
void split(int o,int k,int &a,int &b){
if(!o){
a=b=0;
return;
}else if(k<=size[lc]){
b=o;
split(lc,k,a,lc);
pu(o);
}else{
a=o;
split(rc,k-size[lc]-1,rc,b);
pu(o);
}
}
int merge(int a,int b){
if(!a) return b;
if(!b) return a;
if(fix[a]<fix[b]){
son[a][1]=merge(son[a][1],b);
pu(a);
return a;
}else{
son[b][0]=merge(a,son[b][0]);
pu(b);
return b;
}
}
void insert(int pos,int v){
int a,b,t=node(v);
split(root,pos,a,b);
root=merge(merge(a,t),b);
}
int get(int k){
int a,b,x,y;
split(root,k-1,a,b);
split(b,1,x,y);
int t=x;
root=merge(a,merge(x,y));
return t;
}
}treap;
int n,m,a[MAXN];
int main(){
while(cin>>n>>m){
treap.init();
rep(i,1,n) a[i]=read();
rep(i,1,n){
treap.insert(i,a[i]);
}
rep(i,1,m){
int x; cin>>x;
int pos=treap.get(x);
cout<<treap.val[pos]<<endl;
}
}
return 0;
}
树形操作
BZOJ - 3224
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int MAXN = 2e5+11;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
typedef long long ll;
const ll MOD = 1e9+7;
unsigned int SEED = 19260817;
ll read(){
ll x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline int Rand(){
SEED=SEED*1103515245+12345;
return SEED/65536;
}
struct Treap{
int son[MAXN][2],root,tot;
int val[MAXN],fix[MAXN],size[MAXN];
#define lc son[o][0]
#define rc son[o][1]
void init(){
root=0;
son[0][0]=son[0][1]=0;
val[0]=fix[0]=size[0]=0;
tot=1;
}
int node(int v){
son[tot][0]=son[tot][1]=0;
val[tot]=v; fix[tot]=Rand();
size[tot]=1;
return tot++;
}
void pu(int o){
size[o]=size[lc]+size[rc]+1;
}
void split(int o,int pivot,int &a,int &b){
if(!o){
a=b=0;
return;
}else if(val[o]>pivot){
b=o;
split(lc,pivot,a,lc);
pu(o);
}else{
a=o;
split(rc,pivot,rc,b);
pu(o);
}
}
int merge(int a,int b){
if(!a) return b;
if(!b) return a;
if(fix[a]<fix[b]){
son[a][1]=merge(son[a][1],b);
pu(a);
return a;
}else{
son[b][0]=merge(a,son[b][0]);
pu(b);
return b;
}
}
void insert(int v){
int a,b,t=node(v);
split(root,v,a,b);
root=merge(merge(a,t),b);
}
void del(int x){
int a,b,c,d;
split(root,x,a,b);
split(a,x-1,c,d);
d=merge(son[d][0],son[d][1]);//d的根不要了
root=merge(merge(c,d),b);
}
int krank(int k){
int a,b;
split(root,k-1,a,b);
int res=size[a]+1; //最小的相同数必然是恰比k-1子树规模大
root=merge(a,b);
return res;
}
int kth(int k){
int o=root;
while(1){
if(k<=size[lc]){
o=lc;
}else if(k==size[lc]+1){
return o;
}else{
k-=size[lc]+1;
o=rc;
}
}
}
int kth(int o,int k){
while(1){
if(k<=size[lc]){
o=lc;
}else if(k==size[lc]+1){
return o;
}else{
k-=size[lc]+1;
o=rc;
}
}
}
int pre(int x){
int a,b;
split(root,x-1,a,b);
int t=kth(a,size[a]);
root=merge(a,b);
return t;
}
int succ(int x){
int a,b;
split(root,x,a,b);
int t=kth(b,1);
root=merge(a,b);
return t;
}
}tp;
int n,m,a[MAXN];
int main(){
while(cin>>n){
tp.init();
rep(i,1,n){
int op=read();
int x=read();
switch(op){
case 1:tp.insert(x);break;
case 2:tp.del(x);break;
case 3:println(tp.krank(x));break;
case 4:println(tp.val[tp.kth(x)]);break;
case 5:println(tp.val[tp.pre(x)]);break;
case 6:println(tp.val[tp.succ(x)]);break;
}
}
}
return 0;
}
区间操作+简单标记
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int MAXN = 2e5+11;
const double EPS = 1e-7;
typedef long long ll;
const ll MOD = 1e9+7;
unsigned int SEED = 19260817;
const ll INF = 1ll<<60;
ll read(){
ll x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline int Rand(){
SEED=SEED*1103515245+12345;
return SEED/65536;
}
struct Treap{
int son[MAXN][2],root,tot;
int val[MAXN],fix[MAXN],size[MAXN];
ll mx[MAXN];
#define lc son[o][0]
#define rc son[o][1]
void init(){
root=0;
son[0][0]=son[0][1]=0;
val[0]=fix[0]=size[0]=0;
mx[0]=-INF;
tot=1;
}
int node(int v){
son[tot][0]=son[tot][1]=0;
val[tot]=v; fix[tot]=Rand();
size[tot]=1;mx[tot]=v;
return tot++;
}
void pu(int o){
size[o]=size[lc]+size[rc]+1;
mx[o]=max((ll)val[o],mx[lc]);
mx[o]=max(mx[o],mx[rc]);
}
void split(int o,int k,int &a,int &b){
if(!o){
a=b=0;
return;
}else if(k<=size[lc]){
b=o;
split(lc,k,a,lc);
pu(o);
}else{
a=o;
split(rc,k-size[lc]-1,rc,b);
pu(o);
}
}
int merge(int a,int b){
if(!a) return b;
if(!b) return a;
if(fix[a]<fix[b]){
son[a][1]=merge(son[a][1],b);
pu(a);
return a;
}else{
son[b][0]=merge(a,son[b][0]);
pu(b);
return b;
}
}
void insert(int pos,int v){
int a,b,t=node(v);
split(root,pos,a,b);
root=merge(merge(a,t),b);
}
}tp;
int main(){
int n;
while(cin>>n){
tp.init();
rep(i,1,n){
int x,y;
cin>>x>>y;
tp.insert(x,y);
}
rep(i,1,n){
int a,b,x,y;
tp.split(tp.root,i-1,a,b);
tp.split(b,3,x,y);//[i,i+2]的最大值
// cout<<tp.val[x]<<" "<< //此时val已经无意义
cout<<tp.mx[x]<<endl;
tp.root=tp.merge(a,tp.merge(x,y));
}
}
return 0;
}
//如果插入i区间表示原来i后面插入
