【题解】文艺平衡树 Leafy Tree BZOJ – 3223

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;
}