文艺平衡树
题目描述
核心思路
这题可以使用FHQ Treap来处理维护区间操作问题。如果不了解FHQ Treap，请移步这篇博客：传送门
那么FHQ Treap是如何处理维护区间操作问题呢？例如，要操作的区间为 [ l , r ] [l,r] [l,r]，那么我们就在fhq Treap里把这一段直接split拆出来进行操作然后再合并回去即可。
这里是采用按大小分裂：把树拆成两棵树，其中一棵树的大小等于给定的大小，剩余部分在另外一颗树里
对于区间 [ l , r ] [l,r] [l,r]来说，其实就是：
- 按大小 l − 1 l-1 l−1将root数分裂成x树和y树，那么根据按大小分裂原则可知，x树的大小其实就是 l − 1 l-1 l−1， y y y树的大小是 ≥ l \geq l ≥l的
- 然后按大小 r − l + 1 r-l+1 r−l+1将上面得到的y树分裂成y树(为了以示区分，我们下面将这次分裂得到的y树记录为 y ′ y' y′树）和z树，那么根据按大小分裂原则可知，此时 y ′ y' y′树的大小就是我们需要操作的区间 [ l , r ] [l,r] [l,r]了，那么我们对 y ′ y' y′树进行操作就好了
- 最后把x树，y树，z树合并回去就好了
知道了fhq Treap怎么处理区间问题，怎么来解决文艺平衡树问题呢？
我们需要使用线段树中常见的概念：懒标记。每当我们想要对一个区间进行翻转时，我们就对这个区间维护懒标记：如果原来没有懒标记，那就打上；如果原来有懒标记，那就去掉，因为翻转两次等于没有翻转嘛。这里可以使用异或运算来实现。
那么什么时候需要下传懒标记呢？如果当前结点的左右子树在后续代码中有被更改的风险的话，那就下传，以防万一
其实按大小分裂的FHQ Treap和按值分裂的FHQ Treap大体上是一样的
代码
#include<iostream>
#include<cstring>
#include<random>
#include<algorithm>
using namespace std;
const int N=1e5+10;
std::mt19937 rnd(233);
struct Node{
int l,r; //左孩子节点的编号 右孩子节点的编号 编号其实就是下标
int val; //该节点内的权值
int key; //该节点的随机索引 即随机优先级
int size; //以该节点为根的所形成的树的大小
bool flag; //标记该节点是否需要被翻转
}tr[N];
//idx给每个节点分配的编号(下标) 最后它记录的就是这棵树中节点的总个数
//root记录的就是这棵树的根节点
int idx,root;
//建立新节点 给该节点分配编号
int newnode(int val)
{
tr[++idx].val=val; //记录该节点的值为val
tr[idx].key=rnd(); //随机生成该节点的优先级
tr[idx].size=1; //以该节点为根的树的大小为1
return idx; //返回分配给该节点的编号idx
}
//更新节点的信息 记录以该节点u为根的树的大小
void update(int u)
{
tr[u].size=tr[tr[u].l].size+tr[tr[u].r].size+1;
}
//下放懒标记
void pushdown(int u)
{
//要翻转整颗子树，要先把左右两个儿子翻转，
//然后把懒标记继续下传给左右子树 就相当于递归翻转左右两棵子树
swap(tr[u].l,tr[u].r);
tr[tr[u].l].flag^=1; //把懒标记下传给左子树
tr[tr[u].r].flag^=1; //把懒标记下传给右子树
tr[u].flag=false; //清空当前节点的懒标记
}
//按大小siz将u树分裂成x树和y树
//这里用 引用 将分裂得到的x树和y树 返回回去
void split(int u,int siz,int &x,int &y)
{
//如果要分裂的当前这棵u树是不存在的 那么不可能分裂出x树和y树
//所以把x和y都设为0
if(!u)
x=y=0;
else
{
//有可能被更改 所以需要下放懒标记
if(tr[u].flag)
pushdown(u);
//如果当前节点u的左子树的大小tr[tr[u].l].size比给定的siz小
//由于有可能当前节点u的右子树中存在大小比给定的siz小 所以还需要对u的右子树递归分裂
//注意对u的右子树递归分裂时 要把左子树的大小和节点u都减去 这样才是右子树的siz
if(tr[tr[u].l].size<siz)
{
x=u;
//按大小siz-tr[tr[u].l].size-1将tr[u].r右子树分裂成 tr[u].r树 和y树
split(tr[u].r,siz-tr[tr[u].l].size-1,tr[u].r,y);
}
else
{
y=u;
//按大小siz将tr[u].l左子树分裂成x树和tr[u].l树
split(tr[u].l,siz,x,tr[u].l);
}
//分裂完了之后 要记得更新节点信息
update(u);
}
}
//将x树和y树合并 返回的结果是这两棵树合并后的那个根节点
int merge(int x,int y)
{
//如果x树不存在y树存在 那么合并后就只有y树 因此返回y树
//如果y树不存在x树存在 那么合并后就只有x树 因此返回x树
if(!x||!y)
return x+y;
//这里当作是大根堆来处理 写成> 或者>=都可以
//也可以当作小根堆来处理 即写成< <= 那么就是小根堆
if(tr[x].key>tr[y].key)
{
//有可能被更改 所以需要下放懒标记
if(tr[x].flag)
pushdown(x);
tr[x].r=merge(tr[x].r,y);
update(x);
return x;
}
else
{
//有可能被更改 所以需要下放懒标记
if(tr[y].flag)
pushdown(y);
tr[y].l=merge(x,tr[y].l);
update(y);
return y;
}
}
//将区间[l,r]内的数翻转
void reverse(int l,int r)
{
int x,y,z;
//先按大小l-1将root树分裂成x树和y树
split(root,l-1,x,y);
//再按大小r-l+1将y树分裂成y树和z树
split(y,r-l+1,y,z);
//此时y树就是我们需要翻转的区间
tr[y].flag^=1;
//最后把x树,y树,z树合并
root=merge(merge(x,y),z);
}
//中序遍历
void inorder(int u)
{
if(!u) //递归边界
return;
//有可能被更改 所以需要下放懒标记
if(tr[u].flag)
pushdown(u);
inorder(tr[u].l); //左
printf("%d ",tr[u].val); //根
inorder(tr[u].r); //右
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
root=merge(root, newnode(i)); //合并更新根节点
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
reverse(l,r); //将区间[l,r]内的数翻转
}
//将翻转后的序列输出
inorder(root);
return 0;
}