析合树 学习笔记

djwj233 · 2023-01-31 08:13:31 · 个人记录

被迫营业.jpg

由于众所周知的原因，这篇笔记是讲义形式的。

引入

考虑一个题目 CF526F Pudding Monsters：

给定一个 n 阶排列，求它有多少子串满足值域连续。

这个题初等一点的做法很多，可以分治，也可以用线段树配合扫描线完成。这里先介绍后者。

首先我们先定义题中的计数对象为连续段，将其形式化：

• 定义排列 P 中的 [l,r] 为连续段，当且仅当 \nexists x,z\in [l, r], y\notin[l,r], P_x<P_y<P_z。

由于 P 是排列，不难证明：

• 对任意区间 [l,r]，有：\max_{x\in[l,r]} a_x-\min_{x\in[l,r]} a_x\ge r-l。
• 连续段的判定：[l,r] 是连续段，当且仅当上述不等式取等。

这样上面的题就有做法了：

我们从左往右扫描 r，对每个 l 我们维护对应的 (\max-\min)-(r-l)，然后问题转化为数全局有多少数为 0。

先解决询问部分：由上述引理，维护的数非负。因此我们只需要询问最小值及其数量。

再解决维护部分：扫描的过程中每个点对应的 \max/\min 都是可以用单调栈维护的，只需实现区间加的功能。

线段树可以支持上述所有操作，复杂度 \mathcal O(n\log n)。

至此我们在线段树上刻画了连续段的一种形态：上述扫描过程中，r 与其对应的所有最小值出现的 l 组成的 [l,r]。

下称此为连续段的扫描线结构（名字是我自己取的）。

事实上，扫描线结构在大部分 OI 问题中已经足够强大，但在一些问题上这个结构体现的性质不足，做法较为繁琐。

我们引入一种更高等的结构：析合树。

析合树的导出

记 P 的所有连续段为 I_P，我们尝试用一种结构去组合 I_P。

连续段作为一种二维区间，其间最常见的关系是偏序，因此我们考虑用偏序树去概括它们之间的关系。

而在一个排列中，连续段总数的上界是 \Theta(n^2) 的，不能把所有段建出，这要求我们寻找其本原形式。

连续段的性质很好，简单推理可以得到：

• 连续段的性质：若 A,B\in I_P 且 A\cap B\notin \{\varnothing,A,B\}，那么 A\cap B,A\cup B, A\backslash B,B\backslash A\in I_P。

这样我们还可以得到：I_P 是关于子集偏序的有界格，不过这一般没什么大用。

我们尝试寻找所有连续段的一组基，使得基内的段能够（通过某种方式）生成所有连续段。

有一个较简单的构造：

• 定义一个连续段 A 为本原连续段，当且仅当没有 B\in I_P 与 A 互不包含且相交。

不难发现，本原连续段按照偏序关系构成了一棵树，所以它的大小不超过 2n-1，是 \mathcal O(n) 的。

这棵树被称为析合树。那么，连续段在这棵树上呈什么形态呢？

画出一个排列 [5,8,10,7,9,1,2,3,4,6] 对应的树，标出其连续段。注意到连续段的结构和树结构。

根有四个子树，其中 [1,2,3,4] 的每个子区间都是一个连续段，而 [8,10,7,9] 的任意非叶的真子区间都不是连续段。

这启发我们把点分为两类，分别被称为合点和析点：（我觉得这名字取得挺不好）

• 对于每个非叶结点，其每棵子树分别对应值域区间 [l_x,r_x]，我们将所有子树按照 l 排序，设第 i 棵子树排序后位于第 P_i 的位置。
• 如果 P_i 是顺序或逆序，那么定义当前结点为合点，否则定义当前结点为析点。P_i 一般被称为儿子排列。
• 叶子结点可以随意定义为二者之一，主流的定义是合点。

那么析合树的性质也呼之欲出了：

• 对于一个合点，其子树的任意子区间都构成一个连续段。（注意这里子树不可拆分）
• 对于一个析点，其子树的任意长度大于一的真子区间都不是连续段。
• 除此之外没有别的连续段了。

性质的证明留作习题。

这样，我们成功地导出了析合树结构，并用它刻画了所有连续段。

下面我们将展示如何构造一棵析合树。

析合树的构造

朴素实现

考虑采用增量法，每次加入一个点，维护当前的析合森林。

我们用栈维护析合森林的所有根，每次加入一个点时，执行：

1. 判断当前结点能否作为栈顶结点的儿子，如是则执行，并弹出栈顶结点作为当前结点，回到循环头。
2. 否则，判断当前结点能否与栈顶结点合并为一个合点，如是则执行，并弹出栈顶结点，把合并后的结点作为当前结点，回到循环头。
3. 否则，判断当前连续段是否还不是最长的（这可以用扫描线结构完成），如是则把栈顶尽可能少的元素与当前结点作为一个新析点的儿子，并把对应结点全部弹出，把新析点变为待插入结点，回到循环头。
4. 否则退出循环。

实现时 2/3 两部分可以写在一起，总复杂度是 \mathcal O(n\log n) 的，瓶颈在于扫描线结构中的线段树。

附一份 CF526F 的实现，总长度 3K 左右：

#include <bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define cl(a,v) memset(a,v,sizeof(a))

typedef long long ll;

const int INF = 0x3f3f3f3f;
const int N = 3e5 + 10, M = N << 1;

int n, a[N];

struct SegTree { // maintain max - min - r + l
    struct Node {
        int l, r, d; pair<int, int> v;
    } t[N << 2];
    inline void update(int p) {  t[p].v = min(t[p << 1].v, t[p << 1 | 1].v);  }
    inline void apply(int p, int V) {  t[p].v.first += V, t[p].d += V;  }
    inline void pushdown(int p) {
        if(t[p].d) apply(p << 1, t[p].d), apply(p << 1 | 1, t[p].d), t[p].d = 0;
    }
    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r; if(l == r) return t[p].v = make_pair(l, l), void();
        int mid = (l + r) >> 1; build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
        update(p);
    }
    void change(int p, int l, int r, int V) {
        if(l <= t[p].l && t[p].r <= r) return apply(p, V);
        int mid = (t[p].l + t[p].r) >> 1; pushdown(p);
        if(l <= mid) change(p << 1, l, r, V);
        if(r > mid) change(p << 1 | 1, l, r, V);
        update(p);
    }
    pair<int, int> query(int p, int l, int r) {
        if(l <= t[p].l && t[p].r <= r) return t[p].v;
        int mid = (t[p].l + t[p].r) >> 1; pushdown(p);
        if(r <= mid) return query(p << 1, l, r);
        if(l > mid) return query(p << 1 | 1, l, r);
        return min(query(p << 1, l, r), query(p << 1 | 1, l, r));
    }
    int ask(int p, int x) {
        if(t[p].l == t[p].r) return t[p].v.first;
        int mid = (t[p].l + t[p].r) >> 1; pushdown(p);
        return x <= mid ? ask(p << 1, x) : ask(p << 1 | 1, x);
    }
} T;

struct node {
    int l, r; bool typ; // 0 : divide, 1 : combine
    node(int L = 0, int R = 0, int Typ = 0) : l(L), r(R), typ(Typ) {}
} t[M];
int rt, tot, fa[M], rson[M]; vector<int> son[M];
int st[M], top, st1[M], top1, st2[M], top2; // 1 : min, 2 : max

void Build() {
    T.build(1, 1, n);
    fo (i, 1, n) {
        T.change(1, 1, n, -1);
        while(top1 && a[st1[top1]] > a[i])
            T.change(1, st1[top1 - 1] + 1, st1[top1], a[st1[top1]] - a[i]), top1--;
        while(top2 && a[st2[top2]] < a[i])
            T.change(1, st2[top2 - 1] + 1, st2[top2], a[i] - a[st2[top2]]), top2--;
        st1[++top1] = st2[++top2] = i;

        t[++tot] = node(i, i, 0); int cur = tot, lb = T.query(1, 1, i).second;
        while(t[cur].l > lb) {
            int p = st[top]; assert(top);
            if(rson[p] && T.ask(1, t[rson[p]].l) == 0) {
                fa[cur] = p, son[p].push_back(cur), rson[p] = cur;
                assert(t[p].typ), t[p].r = i, top--, cur = p;
            } else {
                tot++, rson[tot] = cur, fa[cur] = tot, son[tot].push_back(cur);
                do fa[st[top]] = tot, son[tot].push_back(st[top]);
                while(T.ask(1, t[st[top--]].l) != 0);
                reverse(son[tot].begin(), son[tot].end());
                t[tot] = node(t[st[top + 1]].l, i, son[tot].size() == 2), cur = tot;
            }
        }
        st[++top] = cur;
    }
    assert(top == 1), rt = st[top];
}

ll ans;

int main()
{
    cin >> n;
    fo(i, 1, n) {  int x, y; scanf("%d%d", &x, &y); a[x] = y;  }
    Build();

    fo(i, 1, tot)
        ans += t[i].typ ? (ll)son[i].size() * (son[i].size() - 1) / 2 : 1LL;
    printf("%lld\n", ans);

    return 0;
}

线性构造法

其实析合树也有 \mathcal O(n) 的建树方法。优化在于：

• 判断一个区间是否合法使用 \mathcal O(n)-\mathcal O(1) RMQ。

• 把线段树找最左边点的过程去掉，改为暴力向前判断，不难发现这是 \mathcal O(n^2) 的。

• 考虑优化这个过程，对于区间（注意不一定是连续段）[l,r]，值域 [x,y]，那么如果有 i>r, x\le a_i\le y 那么向前扩展是无效的；

  （其中求最大的 i 可以利用逆排列的 ST 表完成）

• 在加入段 x 时我们向前不断地扫，直到可以判断向前扩展无效，记录当前位置是 fail_x。

  不难发现，fail_x 之后的部分不会因为后续数的加入而与它们间的一部分组合成一个段，换言之它们之后不可拆分。

• 因此，我们不需要暴力向前扫，只需要在 fail 链上跳即可，这样复杂度被我们优化到了 \mathcal O(n)，证明留给读者。

此外，析合树还可以被用于非排列的任意数列，只需在前面的做法中改造一下，这部分也留为作业。

析合树的应用

析合树在不同的问题中可以扮演不同的角色，但是无论如何都与其结构密不可分。

正所谓“结构决定性质，性质决定用途”，研究析合树时要注意把握其树和排列两个结构进行分析。

树状结构的应用

既然析合树是一种树状结构，那么用以维护分析树状结构的工具基本都可以用于析合树上。

由于树状数据结构内容与本课关联不大，此处仅举两例。

• P4747 [CERC2017]Intrinsic Interval

每次直接找到 [l,l] 和 [r,r] 两个点的 LCA，根据其类型可以得到答案。

利用扫描线结构也是可行的，对每个 r 我们找到最左边的 l 使 [l, r] 合法，记为 L_r。

然后每次询问 [l,r] 时，我们找到 r 右边的第一个 L_x\le l 的点，可以证明答案一定是 [y,x]，把询问挂在 x 上离线下来再扫描线即可。

• CF997E Good Subsegments

析合树做法和上面是类似的，记录每个子树内的结果，从 l-1,r+1 倍增上去计算答案即可。

扫描线做法和 NOIP2022 D 有点类似，具体不再展开。

组合问题

析合树同时也常被看作组合对象进行形态计数，这时可能需要排列结构的介入。

• LOJ 6632

给定 N，对每个 1\le n\le N 求 n 阶析合树形态数。N\le 5000。

由于我们只是要求形态数，所以除了树以外只需要关注每个点是析点还是合点。

不难发现，只要每个析点度至少为 4 都可以构造出对应排列。

因此我们设 f_{x,y} 为根结点度为 y 的答案，y\ge 4 的状态是等价的所以总复杂度 \mathcal O(n^2)。

• CF1089I Interval-Free Permutations

求有多少 n 阶排列连续段数最少。（也就是不存在长度 [2,n-1] 内的连续段）

Subtask 1/2/3：n\le 400/5000/1\times 10^5。

特判掉 n\le 2 后，可以得到根节点一定是析点。

我们考虑所有 n! 种排列里根的种类：

1. 根是析点

只要根的子树数不到 n 都要容斥掉。我们枚举子树数 x\ge 4，这部分的答案就是 \sum_{4\le x<n} f_xg_{n,x}。

其中 g_{x,y} 表示把 x 依次划分为 y 个排列的方案数，有 g_{x,y}=\sum_{z}g_{x-z,y-1}z!。

2. 根是合点

这部分要全部容斥掉。不妨假设它们单调上升，那么每棵子树都需要是单调减的合点或析点。

设这部分的答案是 h_n，那么 h_n 可以由完全背包得到，减去 2h_n 就是答案。直接实现是 \Theta(n^3) 的。

考虑换一种计算方法：设 h_n 是不包含任意一个真前缀连续段（值域也是前缀）的方案数，有 h_n=n!-\sum h_x(n-x)!。

这样需要减去的就是 2\sum h_x(n-x)!，实现更简单。

这个数列是 OEIS A111111，照着上面的神秘公式可以做到 \mathcal O(n^2)。

更优复杂度需要使用拉格朗日反演，见这里。

作业

就是上面留给读者的部分啦！

1. 证明两种点的上述性质；
2. 证明析合树线性构造算法的复杂度；
3. 改造析合树使得其可以适用于非排列的任意数列。
   1. 给出 \Theta(n\log n) 的做法；
   2. 想一想，有没有 \Theta(n) 的做法？
4. 完成这个题目。
5. 完成 CF1205F。
6. 完成 P4566 [CTSC2018]青蕈领主。