非旋转 Treap/fhq Treap
luckydrawbox · · 个人记录
权值版
宏定义
#define fhqT int：以\text{fhqT} 为基本类型维护，可根据自己需要定义，这里实现了以\text{int} 为基本类型的\text{Treap} 。#define pl a[p].l：\text{fhq Treap} 中左子树的简写。#define pr a[p].r：\text{fhq Treap} 中右子树的简写。
常量与变量
函数
FHQ_Treap()：初始化相关信息，不必调用。-
-
-
-
-
-
-
-
-
-
-
#define fhqT int
#define pl a[p].l
#define pr a[p].r
struct FHQ_Treap{
struct Tree{
int l,r;
fhqT val;
int size,dat;
}a[N],e;
int tot,root;
int x,y,z;
int nc[N];
FHQ_Treap(){
root=0;
tot=N-1;
e.l=e.r=e.val=e.dat=e.size=0;
for(int i=1;i<N;i++)
a[i]=e,nc[i]=i;
}
void update(int p){
a[p].size=a[pl].size+a[pr].size+1;
}
int get_new(fhqT val){
int p=tot--;
a[p]=e;
a[p].val=val;
a[p].dat=rand();
a[p].size=1;
return p;
}
void split(int p,fhqT val,int &x,int &y){
if(!p){
x=y=0;
return;
}
if(a[p].val<=val){
x=p;
split(pr,val,pr,y);
}
else{
y=p;
split(pl,val,x,pl);
}
update(p);
}
int merge(int p,int q){
if(!p||!q)
return p+q;
if(a[p].dat<a[q].dat){
a[p].r=merge(a[p].r,q);
update(p);
return p;
}
a[q].l=merge(p,a[q].l);
update(q);
return q;
}
void insert(fhqT val){
split(root,val,x,y);
root=merge(merge(x,get_new(val)),y);
}
void remove(fhqT val){
split(root,val,x,z);
split(x,val-1,x,y);
nc[++tot]=y;
y=merge(a[y].l,a[y].r);
root=merge(merge(x,y),z);
}
fhqT get_val(int p,int rank){
if(rank<=a[pl].size)
return get_val(pl,rank);
if(rank==a[pl].size+1)
return a[p].val;
return get_val(pr,rank-a[pl].size-1);
}
int get_rank(fhqT val){
split(root,val-1,x,y);
int ans=a[x].size+1;
root=merge(x,y);
return ans;
}
fhqT get_pre(fhqT val){
split(root,val-1,x,y);
fhqT ans=get_val(x,a[x].size);
root=merge(x,y);
return ans;
}
fhqT get_next(fhqT val){
split(root,val,x,y);
fhqT ans=get_val(y,1);
root=merge(x,y);
return ans;
}
void write(int p){
if(pl)
write(pl);
printf("%d %d %d %d %d %d\n",p,a[p].val,pl,pr,a[pl].val,a[pr].val);
if(pr)
write(pr);
}
}tree;区间版
以P2042 [NOI2005] 维护数列为标准。
宏定义
#define fhqT int：以\text{fhqT} 为基本类型维护，可根据自己需要定义，这里实现了以\text{int} 为基本类型的\text{Treap} 。#define pl a[p].l：\text{fhq Treap} 中左子树的简写。#define pr a[p].r：\text{fhq Treap} 中右子树的简写。
常量与变量
函数
FHQ_Treap()：初始化相关信息，不必调用。-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
#define fhqT int
#define pl a[p].l
#define pr a[p].r
struct FHQ_Treap{
struct Tree{
int l,r;
fhqT val,sum,mx,lmx,rmx;
int size,dat;
int tag1,tag2;
}a[N];
int tot,root;
int x,y,z;
int nc[N];
fhqT add[N];
FHQ_Treap(){
root=0;
tot=N-1;
Tree e;
e.l=e.r=e.val=e.dat=e.size=0;
e.sum=e.tag1=e.tag2=0;e.lmx=e.rmx=e.mx=0;
for(int i=0;i<N;i++)
a[i]=e,nc[i]=i;
}
int get_new(fhqT val){
int p=nc[tot--];
a[p].sum=a[p].mx=a[p].val=val;
a[p].dat=rand();
a[p].size=1;
a[p].tag1=a[p].tag2=a[p].l=a[p].r=0;
a[p].lmx=a[p].rmx=max(0,val);
return p;
}
void pushup(int p){
if(!p)
return;
a[p].size=a[pl].size+a[pr].size+1;
a[p].sum=a[pl].sum+a[p].val+a[pr].sum;
a[p].lmx=max(a[pl].lmx,a[pl].sum+a[p].val+a[pr].lmx);
a[p].rmx=max(a[pr].rmx,a[pr].sum+a[p].val+a[pl].rmx);
a[p].mx=a[pl].rmx+a[p].val+a[pr].lmx;
if(pl)
a[p].mx=max(a[p].mx,a[pl].mx);
if(pr)
a[p].mx=max(a[p].mx,a[pr].mx);
}
void make_same(int p,fhqT c){
a[p].val=c;
a[p].sum=a[p].size*c;
a[p].lmx=a[p].rmx=max(0,a[p].sum);
a[p].mx=max(c,a[p].sum);
a[p].tag1=1;
}
void reverse(int p){
swap(pl,pr);
swap(a[p].lmx,a[p].rmx);
a[p].tag2^=1;
}
void pushdown(int p){
if(!p)
return;
if(a[p].tag1){
if(pl)
make_same(pl,a[p].val);
if(pr)
make_same(pr,a[p].val);
a[p].tag1=0;
}
if(a[p].tag2){
if(pl)
reverse(pl);
if(pr)
reverse(pr);
a[p].tag2=0;
}
}
void split(int p,int rank,int &x,int &y){
if(!p){
x=y=0;
return;
}
pushdown(p);
if(a[pl].size<rank){
x=p;
split(pr,rank-a[pl].size-1,pr,y);
}
else{
y=p;
split(pl,rank,x,pl);
}
pushup(p);
}
int merge(int p,int q){
if(!p||!q)
return p+q;
if(a[p].dat<a[q].dat){
pushdown(p);
a[p].r=merge(a[p].r,q);
pushup(p);
return p;
}
pushdown(q);
a[q].l=merge(p,a[q].l);
pushup(q);
return q;
}
int get_l_to_r(int l,int r){
split(root,l-1,x,y);
split(y,r-l+1,y,z);
return y;
}
void merge_back(){
root=merge(merge(x,y),z);
}
int add_num(int l,int r){
int mid=(l+r)>>1;
if(l^r)
return merge(add_num(l,mid),add_num(mid+1,r));
return get_new(add[l]);
}
void insert(int rank,int n){
split(root,rank,x,y);
root=merge(merge(x,add_num(1,n)),y);
}
void del_num(int p){
if(!p)
return;
nc[++tot]=p;
del_num(pl);
del_num(pr);
}
void remove(int rank,int n){
split(root,rank-1,x,y);
split(y,n,y,z);
del_num(y);
root=merge(x,z);
}
int get_sum(int p){
return a[p].sum;
}
int get_mx(int p){
return a[p].mx;
}
void write(int p){
if(!p)
return;
pushdown(p);
write(pl);
printf("%d %d %d %d %d %d\n",p,a[p].val,pl,pr,a[pl].val,a[pr].val);
write(pr);
}
}tree;