[Ynoi2099] Abpodsss

Fusiyi · 2026-08-15 19:13:19 · 算法·理论

背景

这份思念和「心」

让身为机械的我获得了生命

把这全部

在这 251 秒里...

全部赌上！

不能死

还不能死啊！

这场游戏

是休比赢了哦

A big pile of data structure study summaries.

lxl 给我们上了一周的数据结构，我头都要裂开了，所以写一篇总结缓解一下。

线段树分裂合并

动态开点线段树和权值线段树

先来讲讲动态开点线段树。

动态开点线段树就是在结点有需要的时候才给它建出来，当 n 特别大，动态开点线段树可以很好的节约空间。

而且这东西也不难写，基本上只用在每一个函数里加上一行新建节点就行。

为了进一步节约空间，可以开一个栈记录被删除的节点编号，New() 时优先从栈中取用。

int rub[N], top;
inline int New(){ return top ? rub[top --] : ++ tot; }
inline void Delete(int x){ rub[++ top] = x; }

然后来讲权值线段树。

权值线段树其实就是普通线段树按照值域建树，可以理解成一个可以算一个范围的数的个数的桶。

线段树合并

线段树合并就是将两颗线段树合在一起。

显然我们只能用动态开点线段树，如果用普通的每一次都要将所有节点都遍历一遍，直接 T 飞了。

接下来讲一下原理，非常简单：

从根节点出发递归合并。
当遍历到某个节点，如果其中一颗树没有建这个节点，就说明这个点根本就没有值，不用合并，直接返回另一颗子树。
否则我们继续递归合并。

单次合并最坏复杂度是 O(n)，但总合并过程的复杂度为 O(m \log V)，其中 m 为所有线段树中插入的元素总数，V 为值域大小。因为每个节点最多被合并一次，所以总时间可以接受。

注意：合并的两棵树必须对应相同的值域区间，否则合并结果无意义。

放一下我的代码：

inline int Merge(int x, int y, int l, int r){
    if(!x || !y) return x | y;
    if(l == r){
        t[x] += t[y];
        Delete(y);
        return x;
    }
    int mid = l + r >> 1;
    ls[x] = Merge(ls[x], ls[y], l, mid);
    rs[x] = Merge(rs[x], rs[y], mid + 1, r);
    t[x] = t[ls[x]] + t[rs[x]];
    Delete(y);
    return x;
}

这里 t[x] 维护的是区间内元素个数，所以内部节点为左右儿子之和。如果维护的是最大值等其它信息，叶子合并和内部更新需相应调整。

线段树分裂

这就是合并反着来，思想都是一样的。

inline void split(int x, int &y, ll k){
    // 把 x 的前 k 个元素留在 x 中，剩下的元素移到新树 y 中
    if(!x) return;
    y = New();
    ll v = t[ls[x]];          // 左子树元素个数
    if(k > v)                 // 需要从右子树中再取 (k-v) 个
        split(rs[x], rs[y], k - v);
    else                      // 整个右子树都归 y，交换
        swap(rs[x], rs[y]);
    if(k < v)                 // 需要从左子树中取 k 个
        split(ls[x], ls[y], k);
    t[y] = t[x] - k;          // 更新大小
    t[x] = k;
}

被断开的边最多只会有 \log n 条，所以单次复杂度为 O(\log n)。

例题

P5494 【模板】线段树分裂

P4556 【模板】线段树合并 / [Vani 有约会] 雨天的尾巴

P6623 [省选联考 2020 A 卷] 树

P3586 [POI 2015 R2] 物流 Logistics

线段树进阶

势能线段树

当线段树不能打标记时，我们考虑势能线段树。

势能线段树是一种通过分析暴力修改但不会 T 的线段树，唯一的难点就在于势能分析。

势能线段树的核心是：虽然修改操作看似暴力遍历，但每个元素被“有效修改”的次数存在上界（势能），总修改次数可控。

常见场景：区间开方、区间取模、区间整除等。
实现时，线段树节点额外维护区间最大值（或最小值），若该值已无需修改（如区间最大值 ≤ 1 时开方无效），则直接跳过该区间。
势能分析：例如开方操作，每个数最多开方 O(\log \log A) 次即变为 1，故总复杂度 O((n+q)\log n)。

比如区间取模的势能：若区间最大值小于模数，则整个区间无需修改。否则暴力修改每个数。

设当前数值为 x，模数为 m。取模后新值为 x' = x \bmod m。

结论：x' \le \dfrac{x}{2}。

证明：

分两种情况讨论：

若 m \le \dfrac{x}{2}
则 x' = x \bmod m < m \le \dfrac{x}{2}，所以 x' < \dfrac{x}{2}。

若 m > \dfrac{x}{2}
则 x' = x - m < x - \dfrac{x}{2} = \dfrac{x}{2}。

综上，无论哪种情况，都有：
x' \le \frac{x}{2}

每次取模后数值至少减半，故每个数有效修改 O(\log a) 次。

给个例题：

P4145 上帝造题的七分钟 2 / 花神游历各国

我们发现一个数开方很少次数就能变成 1，于是暴力给每个点进行修改，当修改到 1 时就不改了，这个我们可以通过区间最大值是否为 1 判断。

例题

CF438D The Child and Sequence

HDU6315 Naive Operations

UOJ228 基础数据结构练习题

颜色段均摊

珂朵莉树（Chtholly Tree），又名老司机树 ODT（Old Driver Tree），适用于区间赋值操作（推平）且数据随机的场景，这里主要讲的是它的思想。

P2824 [HEOI2016/TJOI2016] 排序

这题将序列看作由若干个已经有序的连续段组成，每个段用一棵权值线段树维护段内元素，用 set 维护所有段的起始位置和排序方向。排序操作等价于将将几颗线段树合并。

例题

CF444C DZY Loves Colors

P4344 [SHOI2015] 脑洞治疗仪

P3215 [HNOI2011] 括号修复 / [JSOI2011] 括号序列

单侧递归线段树

其核心在于解决一类特殊的区间信息合并问题。

在普通的线段树中，合并两个子区间信息通常只需要 O(1) 的时间。但在某些问题中，合并信息时，一个子区间的贡献，依赖于另一个子区间的某种“状态”。为了计算这个依赖关系，我们需要递归地进入一个子区间进行额外查询。

由于这种递归查询每次只进入左子树或右子树的单侧，其时间复杂度为 O(\log n)。这额外的一次单侧递归，会让单次修改的复杂度从 O(\log n) 变为 O(\log^2 n)。

例题

P9130 [USACO23FEB] Hungry Cow P

P4198 楼房重建

CF1340F Nastya and CBS

线段树分治

思想

当一个操作在一个时间段上，我们考虑线段树分治。

线段树分治是一种离线算法，我们对时间建一颗线段树，树的节点存的信息是覆盖了这个区间的操作。

我们遍历这颗树，在递归时进行操作，回溯时撤销操作。

当到达叶子节点的时候计算答案。

例题

P5787 【模板】线段树分治 / 二分图

LibreOJ121 动态图连通性

CF1814F Communication Towers

平衡树

没啥好讲的，基本上除了区间翻转其他的都可以用线段树做。

FHQ Treap

支持分裂合并，和线段树的方式是一模一样的。

inline void split(int id, int siz, int &a, int &b){
    if(!id){
        a = b = 0;
        return;
    }
    push_down(id);

    if(siz <= t[l[id]].siz) b = id, split(l[id], siz, a, l[id]);
    else a = id, split(r[id], siz - t[l[id]].siz - 1, r[id], b);

    push_up(id);
}

inline int Merge(int a, int b){
    if(!a || !b) return a | b;
    int ans;
    push_down(a);
    push_down(b);

    if(t[a].pos > t[b].pos) r[a] = Merge(r[a], b), ans = a;
    else l[b] = Merge(a, l[b]), ans = b;

    push_up(ans);
    return ans;
}

例题

P5066 [Ynoi Easy Round 2014] 人人本着正义之名

笛卡尔树

定义

笛卡尔树是一种二叉树，同时满足以下性质：

中序遍历为原数组顺序（即下标从小到大）。
满足堆性质，每个节点的值大于或小于其左右子树中所有节点的键值。
每个节点对应原数组中的一个位置，左右子树分别对应该位置左侧和右侧的子区间。
说白了就是一个 treap。

构造

使用单调栈 O(n) 建树（以下为小根堆示例，父节点值小于子节点）：

从左到右遍历数组元素 a_i。
维护一个栈，栈内节点按从栈底到栈顶值递增排列。
对于新元素 a_i，新建节点 u。
记录一个 last = 0，用于保存上一个被弹出的节点。
当栈非空且栈顶节点键值 > a_i 时，不断弹出栈顶，并将弹出的节点作为 last（最后一个被弹出的节点成为 u 的左子树）。
若栈非空，则栈顶节点的右子树指向 u（因为 u 在栈顶节点右侧）。
将 u 压入栈。
遍历结束后，栈底节点即为笛卡尔树的根。

参考代码：

for(int i = 1, k; i <= n; i ++){
    k = stc;
    while(k && a[st[k]] > a[i]) k --;  // 小根堆：弹出比 a[i] 大的
    if(k) r[st[k]] = i;                // i 成为栈顶的右儿子
    if(k < stc) l[i] = st[k + 1];      // 最后一个弹出的成为 i 的左儿子
    st[++ k] = i;
    stc = k;
}
// 根为 st[1]

应用

笛卡尔树的典型应用是分治。

每次中点选在数组的极最大值或最小值，统计跨越该点的答案，再递归左右两边（即笛卡尔树的左右子树）。

对于与最大值或最小值的计算极其方便。

例题

P4755 Beautiful Pair

AT_abc282_h [ABC282Ex] Min + Sum

CF549F Yura and Developers

Kruskal重构树

定义

在 Kruskal 求最小生成树的过程中，每次合并两个连通块时，新建一个虚点作为这两个连通块根节点的父亲，虚点的点权设为这条合并边的边权。最终形成的包含原始节点（叶子）和虚点（内部节点）的树，就是Kruskal重构树。

这可以非常方便的求出两点路径上的边权最值。

性质

原始节点全是叶子，虚点全是内部节点。
点权从叶子到根单调不降（最小生成树）或单调不增（最大生成树）。
两点 LCA 的点权 = 原图两点间所有路径中最大边权的最小值。

例题

P2245 星际导航

P4768 [NOI2018] 归程

P4899 [IOI 2018] werewolf 狼人

P7834 [ONTAK2010] Peaks 加强版

后记

别颓了快去学习！