可持久化文艺平衡树
前置知识
变量意义
const int o_o=1e6+10;//数组大小
const int m_a=0x3f3f3f3f;//极大值
int n;//操作次数
int x_p;//新节点编号
long long l_t;//上一次输出结果（用于数据解密）
mt19937 m_t(time(0));//随机数种子
struct node{
int i_d;//随即优先级
int s_z;//子树大小
int l_n;//懒标记（左右儿子互换）
long long v;//节点价值
long long s_m;//区间和
int l,r;//区间左右端点
}t_r[o_o<<4];
int g_i[o_o];//每个时刻的根节点（主席树） 大体思路
- 写出基本的 fhq-treap 合并操作
- 写出基本的 fhq-treap 分裂操作
- 完成基本插入操作
- 完成基本删除操作
- 节点更新时，同时更新区间和标记
- 在插入，合并操作中加入释放懒标记操作
- 写出释放懒标记操作
- 写出区间翻转操作
- 写出求区间和操作
注意：释放懒标记。
合并，分裂操作
void f_l(int p,int k,int &x,int &y){//分裂
if(!p){
x=y=0;//节点不存在
return;
}
p_d(p);//释放懒标记
if(t_r[t_r[p].l].s_z<k){//按排名分裂
x=c_d(p);//继承信息
f_l(t_r[x].r,k-t_r[t_r[p].l].s_z-1,t_r[x].r,y);//继续在右子树分裂
u_p(x);//更新节点信息
}else{
y=c_d(p);//继承信息
f_l(t_r[y].l,k,x,t_r[y].l);//去左子树分裂
u_p(y);//更新节点信息
}
}
int h_b(int x,int y){//合并
if(!x||!y)return x+y;//子树不全，直接合并
p_d(x);//释放懒标记
p_d(y);//释放懒标记
if(t_r[x].i_d<t_r[y].i_d){
t_r[x].r=h_b(t_r[x].r,y);//优先级高的当父节点
u_p(x);//更新节点信息
return x;//返回当前节点
}else{
t_r[y].l=h_b(x,t_r[y].l);//优先级高的当父节点
u_p(y);//更新节点信息
return y;//返回当前节点
}
}注意操作前释放懒标记。
开点，更新节点
int n_w(long long v=0){//动态开点
t_r[++x_p].v=v;//赋初值
t_r[x_p].s_m=v;//赋初值
t_r[x_p].i_d=m_t()%(o_o<<1);//随即优先级
t_r[x_p].s_z=1;//初始化子树大小
return x_p;//返回编号
}
int c_d(int p){//开新点并复制原点信息
int k=n_w();//开新点
t_r[k]=t_r[p];//赋值节点信息
return k;//返回节点编号
}
void u_p(int p){//更新节点信息
t_r[p].s_z=t_r[t_r[p].l].s_z+t_r[t_r[p].r].s_z+1;//更新子树大小
t_r[p].s_m=t_r[t_r[p].l].s_m+t_r[t_r[p].r].s_m+t_r[p].v;//更新区间和
}释放懒标记
注意交换左右子树之前建新节点，保留历史记录。
void p_d(int p){//释放懒标记
if(!t_r[p].l_n)return;//没有懒标记，返回
if(t_r[p].l)t_r[p].l=c_d(t_r[p].l);//建立新节点（维护历史信息）
if(t_r[p].r)t_r[p].r=c_d(t_r[p].r);//建立新节点（维护历史信息）
swap(t_r[p].l,t_r[p].r);//交换左右子树
if(t_r[p].l)t_r[t_r[p].l].l_n^=1;//下传懒标记
if(t_r[p].r)t_r[t_r[p].r].l_n^=1;//下传懒标记
t_r[p].l_n=0;//释放完成
}代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<cctype>
#include<ctime>
using namespace std;
long long r_r(){//快读
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=1e6+10;//数组大小
const int m_a=0x3f3f3f3f;//极大值
int n;//操作次数
int x_p;//新节点编号
long long l_t;//上一次输出结果（用于数据解密）
mt19937 m_t(time(0));//随机数种子
struct node{
int i_d;//随即优先级
int s_z;//子树大小
int l_n;//懒标记（左右儿子互换）
long long v;//节点价值
long long s_m;//区间和
int l,r;//区间左右端点
}t_r[o_o<<4];
int g_i[o_o];//每个时刻的根节点（主席树）
int n_w(long long v=0){//动态开点
t_r[++x_p].v=v;//赋初值
t_r[x_p].s_m=v;//赋初值
t_r[x_p].i_d=m_t()%(o_o<<1);//随即优先级
t_r[x_p].s_z=1;//初始化子树大小
return x_p;//返回编号
}
int c_d(int p){//开新点并复制原点信息
int k=n_w();//开新点
t_r[k]=t_r[p];//赋值节点信息
return k;//返回节点编号
}
void u_p(int p){//更新节点信息
t_r[p].s_z=t_r[t_r[p].l].s_z+t_r[t_r[p].r].s_z+1;//更新子树大小
t_r[p].s_m=t_r[t_r[p].l].s_m+t_r[t_r[p].r].s_m+t_r[p].v;//更新区间和
}
void p_d(int p){//释放懒标记
if(!t_r[p].l_n)return;//没有懒标记，返回
if(t_r[p].l)t_r[p].l=c_d(t_r[p].l);//建立新节点（维护历史信息）
if(t_r[p].r)t_r[p].r=c_d(t_r[p].r);//建立新节点（维护历史信息）
swap(t_r[p].l,t_r[p].r);//交换左右子树
if(t_r[p].l)t_r[t_r[p].l].l_n^=1;//下传懒标记
if(t_r[p].r)t_r[t_r[p].r].l_n^=1;//下传懒标记
t_r[p].l_n=0;//释放完成
}
void f_l(int p,int k,int &x,int &y){//分裂
if(!p){
x=y=0;//节点不存在
return;
}
p_d(p);//释放懒标记
if(t_r[t_r[p].l].s_z<k){//按排名分裂
x=c_d(p);//继承信息
f_l(t_r[x].r,k-t_r[t_r[p].l].s_z-1,t_r[x].r,y);//继续在右子树分裂
u_p(x);//更新节点信息
}else{
y=c_d(p);//继承信息
f_l(t_r[y].l,k,x,t_r[y].l);//去左子树分裂
u_p(y);//更新节点信息
}
}
int h_b(int x,int y){//合并
if(!x||!y)return x+y;//子树不全，直接合并
p_d(x);//释放懒标记
p_d(y);//释放懒标记
if(t_r[x].i_d<t_r[y].i_d){
t_r[x].r=h_b(t_r[x].r,y);//优先级高的当父节点
u_p(x);//更新节点信息
return x;//返回当前节点
}else{
t_r[y].l=h_b(x,t_r[y].l);//优先级高的当父节点
u_p(y);//更新节点信息
return y;//返回当前节点
}
}
int main(){
n=r_r();
int n_g=0;//主席树，时间根
int x,y,z;//分裂操作备用根节点
for(int i=1;i<=n;i++){
int v=r_r(),op=r_r();
if(op==1){//插入
long long p=r_r(),k=r_r();
p^=l_t;
k^=l_t;//解密
f_l(g_i[v],p,x,y);//将 g_i[v] 为根节点的树，按 p 分裂成以 x,y 为根的子树
g_i[++n_g]=h_b(h_b(x,n_w(k)),y);//将新节点合并入树
}else if(op==2){//删除
long long p=r_r();
p^=l_t;//解密
f_l(g_i[v],p,x,z);//将 g_i[v] 为根节点的树，按 p 分裂成以 x,z 为根的子树
f_l(x,p-1,x,y);//将 x 为根节点的树，按 p-1 分裂成以 x,y 为根的子树
g_i[++n_g]=h_b(x,z);//将树合并回去，直接存入新节点
}else if(op==3){//翻转区间
long long l=r_r(),r=r_r();
l^=l_t;
r^=l_t;//解密
//将区间的子树分裂出来（释放懒标记）
f_l(g_i[v],r,x,z);
f_l(x,l-1,x,y);
t_r[y].l_n^=1;//打懒标记
g_i[++n_g]=h_b(h_b(x,y),z);//合并回去（合并前会释放懒标记）
}else {//区间和
long long l=r_r(),r=r_r();
l^=l_t;
r^=l_t;//解密
//前要求的范围分裂出来
f_l(g_i[v],r,x,z);
f_l(x,l-1,x,y);
printf("%lld\n",l_t=t_r[y].s_m);//输出区间和大小
g_i[++n_g]=h_b(h_b(x,y),z);//合并回去
}
}
return 0;
}
