Upd：本文章因代码写太丑被大佬 D 了请谨慎查看
题面就不多说了 https://www.mina.moe/BZPRO/JudgeOnline/3223.html
这个怎么说呢，得用 Leafy Tree 提取区间
可是 ctsc2018 的论文集并没有讲 Leafy Tree 怎么区间操作
提取区间又不能 Splay 到根就只能像无旋 Treap 一样 Split 咯
可是 Leafy Tree 得保持其完全二叉树的性质
于是 Split 就不是你想分就分，Split 的时候还得 Merge 保持性质
比如你把一个点的左子树 Split 成了 A 树和 B 树，为了保证当前节点有俩儿子就得把 B 树和当前节点的右子树合并 Merge 起来
Merge 也比较麻烦。如果当前是 Merge(a, b)，如果 a 树和 b 树已经加权平衡了（$Max(a.size, b.size) \leq Min(a.size, b.size) \times \alpha$）那就直接新建一个节点作为 a 和 b 的父亲然后返回该点。
如果还没有平衡的话就判断以下哪种情况能达到平衡：
- 如果 a 树大一些：
- 第一种：把 b 与 a 的右子树合并
- 第二种：把 b 与 a 的右子树的右子树合并，把 a 的左子树与 a 的右子树的左子树合并（相当于旋转了一下），再把它们合并起来
- 如果 b 树大一些：
- 第一种：把 a 与 b 的左子树合并
- 第二种：把 a 与 b 的左子树的左子树合并，把 b 的右子树与 b 的左子树的右子树合并（相当于旋转了一下），再把它们合并起来
反正就是挺麻烦的……
接着 Merge 会新建节点啊，新建的还不少，得辣鸡回收，不然爆空间
可是回收起来又很麻烦，每次 Merge(a, b)的时候 a 和 b 中有一个的指针会失效，就得丢到辣鸡栈里
然后 Split(a)的时候 a 的指针也会失效得丢到辣鸡栈里
最后 Merge 的时候会新建蛮多节点因此我建议开 3 倍节点
……
你干嘛不写 Splay 啊，想可持久化有无旋 Treap 啊……
其实 Leafy Tree 就是线段树哇你要用线段树实现文艺平衡树你这不是自虐吗
#include <bits/stdc++.h>
#define NS (100005)
#define FIR first
#define SEC second
using namespace std;
typedef pair<int, int> PII;
const int alp = 4;
template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}
struct N {int d, s[2], sz; bool tag;} e[NS * 3];
int n, m, A[NS], root, sz;
stack<int> rub; // 辣鸡栈
int New(int d) // 新建节点
{
int tmp;
if (rub.empty()) tmp = ++sz;
else tmp = rub.top(), rub.pop();
e[tmp].d = d, e[tmp].sz = 1, e[tmp].s[0] = e[tmp].s[1] = e[tmp].tag = 0;
return tmp;
}
void Del(int a) {rub.push(a);} // 排队求回收
void pup(int a) // push up
{
if (!e[a].s[0]) return;
e[a].sz = e[e[a].s[0]].sz + e[e[a].s[1]].sz;
}
void pdown(int a) // push down
{
if (!e[a].s[0]) return;
if (e[a].tag)
{
swap(e[e[a].s[0]].s[0], e[e[a].s[0]].s[1]);
swap(e[e[a].s[1]].s[0], e[e[a].s[1]].s[1]);
e[e[a].s[0]].tag ^= 1, e[e[a].s[1]].tag ^= 1, e[a].tag = 0;
}
}
int Mix(int a, int b) // 新建一个节点作为 a,b 的父亲
{
int tmp = New(0);
e[tmp].s[0] = a, e[tmp].s[1] = b, pup(tmp);
return tmp;
}
int Build(int l, int r) // 建树
{
int a = New(0);
if (l == r) {e[a].sz = 1, e[a].d = l; return a;}
int mid = (l + r) >> 1;
e[a].s[0] = Build(l, mid), e[a].s[1] = Build(mid + 1, r), pup(a);
return a;
}
int Merge(int a, int b) // 合并两颗 Leafy Tree
{
if (!a || !b) return (a | b);
if (max(e[a].sz, e[b].sz) <= min(e[a].sz, e[b].sz) * alp) return Mix(a, b); // 平衡了
if (e[a].sz > e[b].sz) // a 的 size 更大
{
pdown(a);
if (e[e[a].s[1]].sz + e[b].sz <= e[e[a].s[0]].sz * alp) // 如果第一种合并已经平衡了
{
int tmp = Merge(e[a].s[0], Merge(e[a].s[1], b));
Del(a);
return tmp;
}
pdown(e[a].s[1]); // 第一种合并不平衡，只能用第二种了
int x = Merge(e[a].s[0], e[e[a].s[1]].s[0]);
int y = Merge(e[e[a].s[1]].s[1], b);
int tmp = Merge(x, y);
Del(a);
return tmp;
}
else // 同上
{
pdown(b);
if (e[a].sz + e[e[b].s[0]].sz <= e[e[b].s[1]].sz * alp)
{
int tmp = Merge(Merge(a, e[b].s[0]), e[b].s[1]);
Del(b);
return tmp;
}
pdown(e[b].s[0]);
int x = Merge(a, e[e[b].s[0]].s[0]);
int y = Merge(e[e[b].s[0]].s[1], e[b].s[1]);
int tmp = Merge(x, y);
Del(b);
return tmp;
}
}
PII Split(int a, int x) // 分离 a 的左边 x 个元素
{
if (!x) return PII(0, a);
if (!e[a].s[0]) return PII(a, 0);
pdown(a); PII tmp;
if (x <= e[e[a].s[0]].sz)
{
tmp = Split(e[a].s[0], x), Del(a);
return PII(tmp.FIR, Merge(tmp.SEC, e[a].s[1])); // 合并保持性质
}
else
{
tmp = Split(e[a].s[1], x - e[e[a].s[0]].sz), Del(a);
return PII(Merge(e[a].s[0], tmp.FIR), tmp.SEC);
}
}
void Rev(int l, int r)
{
PII X = Split(root, l - 1), Y = Split(X.SEC, r - l + 1);
e[Y.FIR].tag ^= 1, swap(e[Y.FIR].s[0], e[Y.FIR].s[1]); // 正常操作
root = Merge(X.FIR, Merge(Y.FIR, Y.SEC));
}
void Dfs(int a) // 输出
{
if (!e[a].s[0]) {printf("%d ", e[a].d); return;}
pdown(a);
Dfs(e[a].s[0]), Dfs(e[a].s[1]);
}
int main(int argc, char const* argv[])
{
IN(n), IN(m);
root = Build(1, n);
for (int i = 1, l, r; i <= m; i += 1) IN(l), IN(r), Rev(l, r);
Dfs(root), putchar(10);
return 0;
}
0 条评论