TJ For 文艺平衡树
Tiffake
·
·
题解
题目描述
给你 n 个数，有 m 次区间翻转操作，最后输出这 n 个数。
### 思路
既然是区间操作，线段树（`WBLT`）凭什么不能维护？
考虑一下区间翻转的对于一堆小区间的影响。可以发现其实质就是将这堆小区间先对调所有的位置顺序，然后再对每个小区间内部翻转。
在线段树上的操作如下图所示：
而对小区间内部翻转，不就相当于不断交换这个区间左区间和右区间吗？这个操作可以简单地打上懒标记维护。
但是该如何实现这样对调一堆区间的操作呢？可以先跑一遍查找组成翻转区间的一堆小区间，然后用栈把他们存下来。接着再跑一遍，把对应的区间改为栈顶的区间，同时打上懒标记即可。由线段树的性质可知，这些小区间的数量是 $O(\log n)$ 的。
不过相信大家也看到了，这样操作会改变线段树的形态，多翻转几次树高就变成 $O(n)$ 了。因此需要采用根据子树大小平衡的 `WBLT` 实现。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
struct node{
int ls,rs,l,r,sz,v;
bool lz,rv;//lz是子区间翻转的懒标记，rv是判断区间是否需要对调的标记
node(){ls=rs=l=r=sz=0;}
}s[N<<2];
int tot,n,m,a[N],tmp[64],top;//tmp维护的是组成询问区间的一堆小区间
inline void crtup(int k,int ls,int rs){//由底向上更正下标
s[rs].l=s[ls].r+1,s[k].r=s[rs].r=s[ls].r+s[rs].sz,s[k].l=s[ls].l;
s[k].sz=s[ls].sz+s[rs].sz;
}
inline void crtdown(int k,int ls,int rs){//由顶向下更正下标
if(!s[ls].sz&&!s[rs].sz)return;
s[ls].l=s[k].l,s[ls].r=s[k].l+s[ls].sz-1;
s[rs].l=s[ls].r+1,s[rs].r=s[k].r;
}
inline void revnode(int&k){//对调某个小区间
return s[k].rv=0,k=tmp[top--],void();
}
inline void merge(int k,int x,int y){
s[k].l=s[x].l,s[k].r=s[y].r,s[k].sz=s[x].sz+s[y].sz;
s[k].ls=x,s[k].rs=y;
}
inline void pushdown(int k){
if(s[k].lz&&s[k].ls&&s[k].rs)swap(s[k].ls,s[k].rs),s[s[k].ls].lz^=1,s[s[k].rs].lz^=1,s[k].lz=0;
//下传懒标记时需要注意判断是否有儿子
crtdown(k,s[k].ls,s[k].rs);
}
inline void equil(int k){//WBLT的平衡操作
int ls=s[k].ls,rs=s[k].rs,x;
if(min(s[ls].sz,s[rs].sz)*3>max(s[ls].sz,s[rs].sz))return;
pushdown(ls),pushdown(rs);
if(s[ls].sz>s[rs].sz)
if(s[s[ls].ls].sz>=s[s[ls].rs].sz)s[k].ls=s[ls].ls,merge(ls,s[ls].rs,rs),s[k].rs=ls;
else pushdown(x=s[ls].rs),merge(ls,s[ls].ls,s[x].ls),merge(x,s[x].rs,rs),s[k].rs=x;
else
if(s[s[rs].ls].sz<=s[s[rs].rs].sz)s[k].rs=s[rs].rs,merge(rs,ls,s[rs].ls),s[k].ls=rs;
else pushdown(x=s[rs].ls),merge(rs,s[x].rs,s[rs].rs),merge(x,ls,s[x].ls),s[k].ls=x;
}
#define ls s[k].ls
#define rs s[k].rs
void build(int k,int l,int r){
s[k].l=l,s[k].r=r;
if(l==r)return s[k].v=l,s[k].sz=1,void();
ls=k<<1,rs=k<<1|1,build(ls,l,(l+r)>>1),build(rs,((l+r)>>1)+1,r);
crtup(k,ls,rs);
}
#define mid s[ls].r
void find(int k,int x,int y){
if(x<=s[k].l&&s[k].r<=y)return tmp[++top]=k,void();
pushdown(k);
if(x<=mid)find(ls,x,y);
if(y>mid)find(rs,x,y);
}
#undef mid
void rev(int k,int x,int y){
if(x<=s[k].l&&s[k].r<=y)return s[k].rv=1,s[k].lz^=1,void();
pushdown(k);
int mid=s[ls].r;
if(x<=mid)rev(ls,x,y);//注意及时更新
if(s[ls].rv)revnode(ls);
if(y>mid)rev(rs,x,y);
if(s[rs].rv)revnode(rs);
crtup(k,ls,rs);
}
void eql(int k,int x,int y){//平衡操作
if(x<=s[k].l&&s[k].r<=y)return;
pushdown(k);
int mid=s[ls].r;
if(x<=mid)eql(ls,x,y);
if(y>mid)eql(rs,x,y);
equil(k);
}
void ask(int k){
if(s[k].l==s[k].r)return cout<<s[k].v<<' ',void();
pushdown(k);
ask(ls),ask(rs);
}
int x,y;
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m,build(1,1,n),tot=n<<2;
while(m--){
cin>>x>>y,x+=s[1].l-1,y+=s[1].l-1;//更正下标
find(1,x,y),rev(1,x,y),eql(1,x,y);
}
ask(1);//输出
return 0;
}
```