用 rope 写文艺平衡树
CuteMurasame
·
·
算法·理论
什么是 rope
rope 是什么？有人说是可持久化线段树，也有人说是块状链表，反正很方便。
其实本题需要的 rope 操作就两个：
名字.append(x)：把 x 添加到 rope 末尾；名字.substr(x,y)：返回一个 rope，是原 rope 在下标^{[1]} [x,x+y) 范围的值形成的 rope，时间复杂度 \mathcal O(\footnotesize{不知道是\ }\normalsize{\log n}\footnotesize{\ 还是\ }\normalsize{\sqrt n}\footnotesize{，反正不是很慢}\normalsize)。
### 本题怎么做
我们需要截取一段区间并翻转，但是翻转的一般做法是 $\mathcal O(n)$ 的。
于是我们考虑用两个 rope：一个记录序列正向的值，一个记录序列反向的值。
然后反转就直接把另一个 rope 的对应区域截取过来就行了，两个 rope 的相加可以用 `+` 号连接。注意反向 rope 也要改。
这里对应的另一个 rope 的区间有点复杂，建议手动模拟一下，不然很容易错。
### 代码
```cpp
#include<bits/stdc++.h>
#include<ext/rope> // 一定要加这个头文件
#define re register
#define rep(i,a,b) for(re int i(a);i<=(b);++i)
#define req(i,a,b) for(re int i(a);i>=(b);--i)
using namespace std;;
static char buf[6000001],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,6000001,stdin),p1==p2)?EOF:*p1++
inline int read(int &num)
{
re int x=0;re int f=0;re char ch=getchar();
while(ch<48||ch>57) f|=ch=='-',ch=getchar();
while(48<=ch&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return num=f?-x:x;
}
using namespace __gnu_cxx;
int n,q,l,r;
rope<int> tree,rtree;
inline void tree_reverse(int l,int r)
{
rope<int> tmp=tree.substr(l+tree.begin(),r+tree.begin());
tree=tree.substr(tree.begin(),l+tree.begin())+rtree.substr(n-r+rtree.begin(),n-l+rtree.begin())+tree.substr(r+tree.begin(),tree.size()+tree.begin());
rtree=rtree.substr(rtree.begin(),n-r+rtree.begin())+tmp+rtree.substr(n-l+rtree.begin(),rtree.size()+rtree.begin());
}
signed main()
{
read(n),read(q);
rep(i,1,n) tree.append(i),rtree.append(n-i+1);
while(q--)
{
read(l),read(r);
tree_reverse(l-1,r);
}
for(auto i:tree) printf("%d ",i);
return 0;
}
```
开 O2 能过，900ms。
### 推荐题目
~~Long Long OJ~~ 似了。
请前往 [Sleeping Cup](http://8.136.99.126/p/P049) 查看。**update 原来链接放错了，已更正**
若想测试较强的完整数据，请在洛谷查看：<https://www.luogu.com.cn/problem/T442649>。