可持久化文艺平衡树
- 空间不够则动态开点
cpp
struct FHQ{
int ls,rs,key,sz,val,sum;
bool rev;
} fhq[N*80];
int root[N],T1,T2,T3,idx;
int newNode(int val=0){
fhq[++idx]={0,0,(int)rng(),1,val,val,0};
return idx;
}
int copyNode(int u){
int p=newNode();
fhq[p]=fhq[u];
return p;
}
void pushup(int u){
fhq[u].sz=fhq[fhq[u].ls].sz+fhq[fhq[u].rs].sz+1;
fhq[u].sum=fhq[fhq[u].ls].sum+fhq[fhq[u].rs].sum+fhq[u].val;
}
void pushrev(int u){
fhq[u].rev^=1;
swap(fhq[u].ls,fhq[u].rs);
}
void pushdown(int u){
if(fhq[u].rev){
if(fhq[u].ls){
fhq[u].ls=copyNode(fhq[u].ls);
pushrev(fhq[u].ls);
}
if(fhq[u].rs){
fhq[u].rs=copyNode(fhq[u].rs);
pushrev(fhq[u].rs);
}
fhq[u].rev=0;
}
}
void split(int u,int k,int &x,int &y){
if(!u){
x=y=0;
return;
}
pushdown(u);
int tmp=fhq[fhq[u].ls].sz+1;
if(k==tmp){
x=copyNode(u);
y=fhq[x].rs;
fhq[x].rs=0;
pushup(x);
}
else if(k<tmp){
y=copyNode(u);
split(fhq[y].ls,k,x,fhq[y].ls);
pushup(y);
}
else{
x=copyNode(u);
split(fhq[x].rs,k-tmp,fhq[x].rs,y);
pushup(x);
}
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(fhq[x].key>fhq[y].key){
pushdown(x);
int u=copyNode(x);
fhq[u].rs=merge(fhq[u].rs,y);
pushup(u);
return u;
}
pushdown(y);
int u=copyNode(y);
fhq[u].ls=merge(x,fhq[u].ls);
pushup(u);
return u;
}
void insert(int &root,int p,int val){
split(root,p,T1,T2);
root=merge(merge(T1,newNode(val)),T2);
}
void erase(int &root,int p){
split(root,p,T1,T2);
split(T1,p-1,T1,T3);
root=merge(T1,T2);
}
void reverse(int &root,int l,int r){
split(root,r,T1,T2);
split(T1,l-1,T1,T3);
pushrev(T3);
root=merge(merge(T1,T3),T2);
}
int query_sum(int &root,int l,int r){
split(root,r,T1,T2);
split(T1,l-1,T1,T3);
int ans=fhq[T3].sum;
root=merge(merge(T1,T3),T2);
return ans;
}