1.题目描述
传送门：here
大意：给你一个序列，让你每次翻转区间\([l,r]\)，并且输出最后的区间
2.思路
1.暴力
每次暴力翻转区间 时间复杂度\(O(n^2)\) 妥妥T
2.平衡树
考虑怎么用splay实现
我们知道平衡树的特性：不管怎么树旋转 它的中序遍历一定是不变的 而且\(BST\)的中序遍历一定是从小到大的
思考如何利用这个性质
翻转区间是什么？
不就是在一段区间遍历中，从左根右变成右根左
这样折腾太麻烦，不如直接交换左右子树位置
怎么找到那一段区间的子树呢？
回忆一下是怎么删除节点的
把前驱翻转到根，后继翻转到根的右节点，那么根节点的右子树的左子树就是要找的点
同理，翻转区间\([l,r]\)，我们把\(l-1\)翻转到根，把\(r+1\)翻转到右子树，此时左子树为对应区间
因为一开始直接给定了序列，可以一开始就建出一棵完美平衡树
同样要插入最小和最大
还有些优化就是为了减少时间复杂度打上懒标记
其他就没什么了
注意：此时满足的是编号的\(BST\) 而不是\(val\)的\(BST\)
Code:
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n,m,a[MAXN];
int tot,root;
int size[MAXN],fa[MAXN],val[MAXN];
int tr[MAXN][2],lz[MAXN];
void Pushup(int x)
{
size[x]=size[tr[x][0]]+size[tr[x][1]]+1;
}
void Pushdown(int x)
{
if(!lz[x]) return;
swap(tr[x][0],tr[x][1]);
lz[tr[x][1]]^=1;
lz[tr[x][0]]^=1;
lz[x]=0;
}
int chk(int x)
{
return tr[fa[x]][1]==x;
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=chk(x),w=tr[x][k^1];
tr[y][k]=w;fa[w]=y;
tr[z][chk(y)]=x;fa[x]=z;
tr[x][k^1]=y;fa[y]=x;
Pushup(y);
Pushup(x);
}
void splay(int x,int goal)
{
while(fa[x]!=goal)
{
int y=fa[x];
int z=fa[y];
if(z!=goal)
if(chk(x)^chk(y)) rotate(x);
else rotate(y);
rotate(x);
}
if(!goal) root=x;
}
int build(int l,int r,int f)
{
if(l>r) return 0;
int now=++tot;
fa[now]=f;
int mid=(l+r)/2;
val[now]=a[mid];
tr[now][0]=build(l,mid-1,now);
tr[now][1]=build(mid+1,r,now);
Pushup(now);
return now;
}
int kth(int k)
{
int now=root;
while(1)
{
Pushdown(now);
if(tr[now][0]&&k<=size[tr[now][0]])
now=tr[now][0];
else if(k>size[tr[now][0]]+1)
{
k-=size[tr[now][0]]+1;
now=tr[now][1];
}
else
return now;
}
}
void print(int now)
{
Pushdown(now);
if(tr[now][0]) print(tr[now][0]);
if(val[now]>=1&&val[now]<=n)cout<<val[now]<<" ";
if(tr[now][1]) print(tr[now][1]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n+1;i++)
a[i+1]=i;
root=build(1,n+2,0);
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
l=kth(l),r=kth(r+2);
splay(l,0);
splay(r,l);
lz[tr[r][0]]^=1;
}
print(root);
return 0;
}