2025 Summer MX

rainbow-auto
  2025-07-14 22:55:16 2025-07-14 22:55:16 Created   2025-09-14 11:19:43 2025-09-14 11:19:43 Updated  

Day 1

upd：模拟赛 210，C 班 rk5，总榜 rk43。

挺困难的。听说一车三四十分的。

T1

一直不确定猜的结论，等到最后半个小时才写的。

实际上证明起来还是挺有意思的。

在第一次操作后，一定有至少一个空瓶。而总和固定，故状态数是线性的。

具体地，满足 的正整数二元组 的数量级是 的。

T2

最喜欢数据结构的一集。

神秘分治。

upd: 这个是猫树 /se

瓶颈实际上在于合并两个计数背包是 的。然而对合并的背包求单点值确实 的。

考虑穿过 的所有询问，此时仅需要将两个背包合并起来求点值。

朴素的多项式乘法是 的，然而若仅需要求一个点值确实 的。

具体地，求 是 的，但对特定的 求 是容易的。

T3

的神秘性质。 与 结构几乎相同。因而可以使用类似的方法考虑。

都是运算后单调不增。

于是可以考察区间 的一种别样刻画。

记 为最小的 ，使得 。

注意到对于特定的 ，有定义的 其实是很少的。因为任意一个较小的 一定是一个较大的 的约数。而每次寻找约数一定会至少使 减半。因此只有 个。

这样实际上就已经可以很容易的支持查询区间 了。枚举分界点即可。

然后对于询问 ，求出 后，实际上需要求出至多有多少个并集为 区间的 为 。

这也应用了邻项合并的性质，最终合并出的序列中每个数对应原序列的一段区间。

因此我们只需要在 上不停的跳就行了，考虑这等价于求树上深度最大的 的祖先。倍增加速即可。

题是好题。

md 我调破防了 /kk

T4

依托。

01-bfs。

考虑最短路更新时，若对当前 已经求出最短路径，则 连出去所有 的边一定是最优的。而 边可能劣于 边。

因而把 放到队头， 放到队尾。

用 std::deque 维护即可。

为啥没有人补 T4 呢？到底是怎么会是呢？

原题有带图的样例解释，为什么搬过来就没有了呢？？

生怕有人得着分了 /cy

T5

可爱题。

T6

处理排列的冒泡排序的利器，考虑 You can't use 'macro parameter character #' in math modex_i = # { p_j > p_i | j < i }

进行一轮冒泡排序后

因为冒泡排序进行到 时，实际上是将前缀的最大值与 进行比较并决定是否交换。

讨论两种情况

  • 恰好是长为前缀 最大值，即 ，那么显然排序后 作为前缀 的最大值不会与之交换，因而

  • 不是前缀 的最大值，此时 ，所以会产生 与 的交换。交换完后， 处为 原来的值，前缀 恰好为前缀 去掉前缀 的最大值，因而

拼起来就是 。

注意到对位置 ，当且仅当 时会产生 的贡献。拆开贡献就能写成

Day 2

线段树？

最喜欢的一集 /cy

鲜花

isui 和 suis 咋唱歌都这么好听。

政治问题，这么深刻。

舍友这么友善。

一言

「你想做什么就做什么，你的目的只是使你的水平提升。当然你什么都不做是不能提升水平的。」 – 10o

「作业本来就是用来帮助你的，而非增加你的负担的。我们的题单你爱做就做。」– 10o

「无论什么理论中，总有这样一个原理：越具体的事物就具有越多的性质。具体就性质多，那么抽象自然就性质少。性质少也就决定了方法少——想想那个我们一无所知的黑盒类型，黑盒修改黑盒查询，最优的算法就只是暴力。」 – _rqy

扫描线

需要记录两个信息，被覆盖的总数 以及大于 的位置数量 。

注意到 是不支持快速修改的。但我们每次仅会查询全局 的和。

upd：上面好像在随机说话。

询问 10o 后得知，显然任何位置都满足 ，想要求 的位置仅需要知道有哪些位置满足 即可。也即考察序列中的最小值即其出现次数。

这就很好写了。

线段树合并

每次递归时一定会删去一个旧点。因而 merge 调用次数不超过总节点数。

并且将 和 合并成 后， 和 都将失效，因此线段树合并的结构必须是树状的，而且应当自底向上。

一个思考如何实现的 trick 是，假装不动态开点，每一个都能遍历到叶子。显然我们通常会获得叶子合并的方法和大区间合并的方法。

考虑优化，当两棵树的当前节点有一个为空时，这个空的节点的权值显然是 。这时候叶子合并可能可以快速完成，因为我们已经知道另一棵树中每个叶子的权值都为 。

线段树合并是有交合并，而线段树分裂是无交分裂。

可持久化线段树

单点修改是平凡的。

懒标记。考虑对点 有子节点 与 ，将 和 复制成 和 ，将 的儿子改为 和 ，下传标记即可。

标记永久化

不对标记进行下放。

那么单点的贡献要加上单点到根的路径的和。

定义节点的 为考虑子树内所有的标记的和。

那么在计算区间贡献的时候需要带上根到当前节点的标记和并乘上当前区间长度。

标记永久化意味着可以随意穿过老标记打新标记，那么就要求标记具有交换律。

或者存在逆元也可以？

线段树上二分

平凡。

猫树

可爱捏。

对于每个节点，维护左子节点的全部后缀信息，右子节点的全部前缀信息。

补成完全二叉树，lca 恰好是最长公共前缀，也就是 x >> log(x xor y)，因为异或会把相同的地方全部消去而不同的地方全都保留。

适用于区间合并困难但是单点合并轻松的问题。

其实就是昨天 T2。

事实上，猫树之类的用于区间半群信息维护的数据结构通常被称为二区间合并数据结构。并且猫树是严格的「二区间」，是因为她真的只会将两个区间合并恰好一次。而线段树等则不然，因为她会将询问区间拆成 个子区间，再进行合并。

线段树分治

可爱。

对于支持撤销的操作。维护时间段。

seg-beats

说好要讲的历史和呢？？？

喜报，开讲了 /cy

分成两个序列，记 为原序列, 为 历史 max

考察信息和标记时，可以考虑全局修改。这是线段树分治结构的目的。

对 , 仅有加法和赋值操作，记录 为加 , 为赋值为 。

赋值操作将会使后面的 操作变为 操作。这还挺重要的，我们将仅仅面临两种情况，而非 inf 种神秘情况。

对 ，仅在同步操作时有影响。若在同步前有赋值，则同步等价于和定值 chkmax，保留最大的同步定值即可。标记一下，记为 。而整体加更为容易， 也将整体加, 记为 。

懒得写了

10o

算了算了上面那个好像还是过于复杂了。

xde 有一个广义矩阵乘法版本 link

扩展域并查集判二分图

这还挺牛的。

扩展域相当于强制构造出一个很好的结构，使得从 走奇数步一定落在与 相同的域中，从 走偶数步一定落在与 相异的域中。那么就很容易判断是否存在奇环了。

并查集，要初始化。

写初始化函数之后要调用。

按秩合并

不是为啥不按秩合并也能过原数据啊？

Day3

凸轮。

鲜花

为啥有小朋友在我右前方刷神秘视频啊。

牛魔的。这个神秘视频晃得我眼睛疼。

神秘诈骗，求 。

棒棒糖好吃。

Tarjan

复习一下。

通过一条非树边不能逃脱子树，那就意味着产生了神秘的结构。

因而我们有了 ，为子树中能够通过一条非树边能够到达的最小 。

割边

显然非树边一定不是割边。

若 的一个子节点 ，满足 ，则 为割边。

割点

根节点若有两个以上儿子，显然是割点。

对于非根节点 ，若存在儿子 ，则 为割点。

边双联通分量

每个点恰好属于一个边双。

点双联通分量

每个点双作为方点，向所有该点双中的点连边。

一个环上的所有点一定属于同一个方点。

若 v-DCC 中存在奇环，则 v-DCC 中的点都会出现在奇环中。

alt text

这也太牛了。

2-SAT

定义: 有一些布尔变量之间的关系式, 求这组布尔变量的一个解

如何做呢?

在图上, 对每个变量真假各建一个点, 如果 能推出 ，则连边 。

发现连出来的边有一定的对称性。

然后缩点后拓扑排序, 按拓扑序推导。

发现推导的时候应该倒序推，又因为 tarjan 用到了栈, 相当于一个反拓扑排序，即 scc 越大, 拓扑序越小, 所以当scc[x] < scc[!x] 时x取true, scc[x] > scc[!x] 时 取 false。

感性理解:

在一个图中，拓扑序越大的点越接近终点，因此选拓扑排序大的点不容易产生矛盾。

如下图, 选 true 只能往下走一个点， 选 false，则有可能到达 选 true 的哪个点

连边时注意推出的顺序: 一条从A的角度考虑, 一条从B的角度考虑

2-SAT 求为真尽可能多的的解是NPC问题

二分图最大匹配

考虑增广路为非匹配边与匹配边交错的路，因此 flip 之后能够恰好将匹配增加

欸为啥网络流做这个更快啊。那我学牛魔的匈牙利算法。

网络流建模技巧

平面网格天生具有二分图性质，可以进行黑白染色。

König 定理

二分图上最大匹配等于最小点覆盖。

这个好像有点显然，因为建图跑最大流的时候会将中间的边流量设为正无穷。

考察最大匹配等于最大流等于最小割。又因为原图变容量为正无穷，因而最小割边集一定不包含二分图上原来含有的边。

相应的，割边集中的所有边都对应着建模时的点。

所以最小点覆盖显然就是割边集的大小。因为这是最小的点集合使得原二分图在取出他们后不剩余任何一条边。

？

最大独立集等于最小点覆盖。

我也不知道这个叫什么。好像是应用了 Dilworth。

并且一个点集为点覆盖的充要条件为她的补集为独立集。反之亦然。

这个也挺显然的。因为点覆盖用点覆盖了所有边，而独立集要求不包含任意一条边。

二分图博弈

设一实例

若 为必须点，则先手赢。

判断是否为必须点时，仅需要对 和 做最大匹配。

联通图容斥

枚举 所在联通块大小。

CF1556F

竞赛图。

考察强联通分量缩点之后的结构，是链。

因而竞赛图的王一定是链首强联通分量中的所有人。

考虑枚举他们的集合 ，则所求期望为 。

考虑

其中 为 构成强联通分量的概率， 为 中所有点都像 中连边的概率。

度数序列

兰道定理

摆掉了。

Erdos-Galli 定理

类似。

Hall 定理

二分图 有 到 的完美匹配，当且仅当任意 ，。

必要性是显然的。

考虑证明 Hall 定理的充分性。

可达性

先强联通分量缩点，得到一个 DAG。

DAG 可达性是不容易的，只能 。

追忆。

Brovuka

每轮扫描所有联通块，将本轮未连过边的联通块连出的最小边连上。

耳分解

每次加入一条从已有点集中的两个点出发，只经过不再当点集中的点，能够形成的

P4581 [BJOI2014] 想法

神中神！

随机化。

Day4

模拟赛。

赛时

  • 8:25 过 t1，期望得分 100pts

  • 9:29 t2 随机树高暴力，期望得分 30 + ? pts

  • 9:39 t4 subtask1，期望得分 1。

牛魔的，为啥这么多人说话？？？？？？？？？？

我是唐氏。

  • 10:45 t3 bitset，期望得分 80pts

  • 11:49 t2 树剖，期望得分 100pts

诶那我咋还有半小时啊。

你咋知道我 300 行代码 10 min 就调完了 /cy

不是为啥要把大阳历答案文件弄成 .out。

摆了。

T3

为啥我 bitset 会有神秘 wa。

我进行别样的 bitset 卡常，得分单调不升。

神人。

T4

题面写的好烂！！！！

读错题了。

那就变成诈骗了。

想要联通块尽可能多，显然的策略是在交集中去除尽可能多的边。

然而每次的边集都必须是联通的。所以想要去除一条边当且仅当原图中去除这条边后依然可以联通。

这与边双联通分量的定义是等价的。

Day5

咋就 Day5 了。

树的重心

存在两个重心的充要条件是有一条边恰好能将树分成两个相等大小的部分。

长链剖分

每次把儿子中子树高度最大的作为长儿子。

长链有一些显然的性质，比如若已确定一组祖先关系，则他们所属的长链长度一定都大于他们的距离。

长剖优化可以优化与深度相关的信息的合并，原因是只与深度相关的信息能够 从长儿子平移到父亲上。

天天爱跑步

[LNOI2014] LCA

发现贡献等价于两条到根链的交集的点数。每次一条加一条查即可。

然后发现实际上只需要求出一个前缀到 的 lca 的深度即可。

扫描线即可。

这个问题提供了一种关于关于 lca 深度的别样刻画。lca 深度等价于树上链交点数。

树上背包

每一对点都会在她们的 lca 处产生贡献。

[FJOI2014] 树的重心

以重心为根重新定型。

  • 两个重心

  • 一个重心

单调栈

感觉先前从来没有人说过这样做的 motivation。

实际上前缀 的单调栈里面存储的是从 向前扫，所有可以 chkmin 的位置。

因为对一个序列，她的后缀最小值是从后向前单调不增的。因而我们仅需维护产生变化的位置，就可还原出这个序列的后缀最小值序列。

并且，后缀最小值发生变化当且仅当在此处产生一个比原最小值更小的值。因而实际上我们能够通过后缀最小值序列获取所有我们想要获取的和后缀相关的最小值信息。

这是很深刻的。

然后有一个很可爱的均摊证明帮助我们动态维护一个单调栈。

欧拉序求 lca

四毛子。

复杂度的 rmq 和 lca！

欧拉序定义为 时所有经过的点的序列，包括重复经过的点。

和 的 lca 为欧拉序上 到 的最小值所对应的位置。

点分治

用于处理与路径相关的问题。

实际上是一个很漂亮的暴力。

考察所有经过经过重心的贡献。

然后对所有子树分治，由重心的性质

CF293E Close Vertices

对条件容斥还是很新颖的。

点分树

对分治中心连边。

点分树完全打乱了原树的所有结构。

边分治

统计经过一条边的所有贡献。

其实这个思想好像很常用啊？但是我先前好像一直不知道这个叫边分治。

当然直接做是不太容易的，但是如果能够把原树三度化。

树上的树

Day6

赛时

赛时 大声 讨论解法的，尼木什么时候死啊。

T1 是流子？？？

哦哦我好唐。

2s 1024MB

最宽松的一集。

10:55 t2 100pts

11:33 t3 25pts

11:55 t1 100pts

牛魔的，模拟 dijkstra 还是太深刻了。

舍友 t4 点分树每个分治中心上挂一棵李超线段树过了。代码长度 7k。神人。

欸我 t1 比 std 多一个 为啥还比他快 倍啊

Day7

这么快！！！

舍友 2min 就教会我 SA 了，这么牛的。

好像没有那么困难。

「梦熊为什么不发 vjudge 题单？」

「他蠢。」

ACAM

考察所有模式串的所有前缀的并集 。

每次实际需要寻找

01-trie

实际上可以理解成值域线段树。

Day8

问号。

8:11 T1 100pts

?????

T2

可以证明 轮置换后一定会产生循环。

每一轮置换结构完全相同。考察置换环即可。

T3

神秘方法优化建图。

具体地，将每位拆开决策。

表示 这个数，前 位已决策过，有 个不同。

连以下三类虚拟边：

然后在 dijkstra 松弛 边时暴力松弛即可。

Day9

CF79D Password

很神秘。

首先首先考虑异或差分。

P5309 [Ynoi2011] 初始化

可爱题。

Day10

休息日。

学习奇怪的东西。

来自 deepseek 对他的解释。

我将从数学基础开始，逐步拆解这篇博客的所有证明，确保每个步骤都清晰可循。以下内容需要线性代数和群论基础，我会补全所有关键定义。

前置数学基础

1. 群表示论核心概念

  • 定义（群表示）：群 在域 上的线性表示是一个同态 ，其中 是 -线性空间。
    等价描述： 作用在 上，且作用保持线性结构（即 ）。

  • 子表示：子空间 若满足 （对所有 )，则称 为子表示。

  • 不可约表示：若 没有非平凡子表示（即只有 和 本身），则称 是不可约表示。

  • 半单性：若表示 可分解为不可约子表示的直和 ，则称 是半单的。

定理1：Maschke定理的完整证明

定理（Maschke）

设 是有限群， 是域，且 （即 在 中可逆），则 的任意 -表示都是半单的。

证明补全：

  1. 目标：对任意表示 和子表示 ，找到另一个子表示 使得 。

  2. 构造投影的“平均化”：

  • 设 是任意投影（即 ），但 未必是 -等变的（即未必满足 ）。
  • 定义新映射 ： 关键点：由于 ，标量 在 中有定义。
  1. 验证 是 -等变：
  • 对任意 ，计算：
    • 令 ，则当 取遍 时 也取遍 ，且 。代入得： 故 是 -等变的线性映射。
  1. **验证 **：
  • 对 ，由于 是子表示，有 ，从而 。代入得：
  1. 构造直和分解：
  • 令 。由于 是 -等变的， 是子表示。
  • 对任意 ，有 ，其中 ，且 （因 )。
  • 若 ，则 且 ，故 。因此 。

结论： 半单。

推论：群代数维数公式

推论

设 的不可约表示为 ${U_i}{i \in I}，则|G| = \sum{i} (\dim U_i)^2$.

证明补全：

  1. 群代数 的结构：
  • 是以 为基的自由 -模，维数为 。
  • 通过左乘作用在 上（正则表示）。
  1. 半单性分解：
  • 由 Maschke 定理， 是半单的，故可分解为不可约子表示的直和：
  1. Schur 引理的应用：
  • 由 Schur 引理，（因为 是域且表示不可约）。
  • 比较代数同构： 其中 是 矩阵代数。
  1. 维数计算：
  • 左端： 作为 -线性空间维数为 (因 维数为 )。
  • 右端： 的维数为 。
  • 故 。
  1. **证明 **：
  • 由不可约表示理论，正则表示中 的重数 等于 （因特征标正交关系 ）。
    代入即得：.

Fourier变换与复杂度分析

Fourier变换定义

对函数 ，其 Fourier 变换定义为：

复杂度优化的直观解释

  1. 朴素乘法：在群代数 中计算乘法需 次运算（因基元素相乘需遍历所有对）。

  2. Fourier 域乘法：

  • 在 Fourier 域中，乘法变为直积分量上的矩阵乘法：
  • 每个 上计算矩阵乘法需 次运算（ 是矩阵乘法指数）。
  • 总复杂度：.
  1. 复杂度对比：
  • 由维数公式 ，当 > 时两种方法同阶。
  • 但若 （如 Strassen 算法 ），Fourier 域更优。

快速 Fourier 变换（FFT）的递归结构

核心思想：限制表示分解

设 是子群，陪集分解 （）。

  1. Fourier 变换的递归表达式：

    其中 是 限制在 上的 Fourier 变换。

  2. 技术难点：基变换
    可能可约，需选择 的基使其限制 呈分块对角形式：

    此基变换需 时间。

  3. 递归复杂度：

Lev定理与复杂度上界

定理（Lev）

若 不是素数阶循环群，则存在真子群 满足 .

复杂度分析（简化版）

  1. 递归假设：取 满足 ，则 .

  2. 递归式：

  3. 维数估计：

  • 由 和 Cauchy-Schwarz 不等式，
  • 又 且 ，故
  1. 最终递归式： 解此递推得 （当 时）。

循环群 FFT：标准 FFT 的由来

设 ，此时不可约表示均为 1 维，对应特征标：

Fourier变换的递归结构

  1. 陪集分解：取子群 （），则 .
    ?

  2. 递归公式：

    解释： 对应 限制在 上。

  3. FFT 的蝶形算法：

  • 当 时，递归树完全平衡。
  • 位逆序原理：下标 的二进制逆序 使得递归基出现在迭代顺序的开头。

总结：从群表示到实际算法

  1. 数学本质：FFT 是群表示论在循环群 上的具体实现。
  2. 复杂度优化根源：半单性（Maschke）保证 Fourier 域可分治；子群结构（Lev）保证高效递归。
  3. 实际应用：选择 使子群链 达到最优分治。

以上证明补全了博客中所有关键步骤。要完全掌握，请尝试对 （对称群）显式计算不可约表示和 Fourier 变换。若有具体步骤需进一步展开，请随时指出！

不是我咋还有一车题没补。

那我补题去了。

我 cf rating 咋这么低。

发现我可能没有常人所拥有的思考能力。

加训点不困难的神秘的思维题。

CF tracker

Day11

Sugoroku2

Link

神中神。

反解。

?

随机游走。

直接 dp 有后效性。

写出状态之间转移的约束，可以考虑高斯消元。

[ABC182F] Valid payments

Link

考虑每一种纸币，要么付，要么找。

不可进位。

Day12

模拟赛。

牛魔的 t1 咋是这么做的。

8:48 t1 100pts

T2

读错题了！！1

T3

两维分步转移，很深刻！

Day13

线性代数。

这么牛。

P8110 [Cnoi2021] 矩阵

结合律。

P3193 [HNOI2008] GT考试

高斯消元

简单。

线性基

构造

终于有人讲明白 oi 中贪心构造的线性基为什么是对的了。

有结论 一个向量组的任意极大线性无关组大小都相同。

最大意味着全局最优，而极大的意思是局部最优。

具体地，在某些连续性优化问题中，极大值点为导数为 的点，而最大值点是定义域内函数值最大的点。

显然最大值点一定是极大值点，而极大点不一定是最大值点。

在某些问题中，贪心构造极大结构是错误的。但由上面的结论，在求极大线性无关组时，极值点与最值点是等价的。

所以随便乱贪就行了。

1
2
3
4
5
6
7
8
9
10
11
12
inline bool ins(Vector a) {
	rep (i, 1, m) {
		if (not a[i]) continue;
		if (not b[i][i]) return b[i] = a, true;

		i64 c = a[i] * inv(b[i][i]) % mod;
		rep (j, i, m) (((a[j] -= c * b[i][j] % mod) %= mod) += mod) %= mod;
	}

	return false;
}

前缀线性基

考察线性基变化的位置只有 个。

因此像单调栈一样记录最后变化的位置即可。

Day14

9:41 T2 100pts

T1

你家模拟赛 开 ？？？？？？？？？？？？？？？

数据范围开成 大家就都会做了。

T2

简单 ds

T3

树形 dp

Day15

欸我咋不会 div2 C 啊

这么恐怖。

加训 /fendou

exgcd

和 同根同源，都是把 转化为 这样的子问题。

考虑求出 的一组特解。

若已知 的一组解 ，则

将 展开成 ，则

整理得

我们不妨令

就结束了。

然而对于一般的不定方程，我们可以先考虑解决

excrt

据说这个比 crt 好理解来着。

excrt 更像是 trick，而非比较牛的算法。

考察同余方程组

我们希望他们被合并成一个。

考虑把他们打开得到

所以有

考虑用 exgcd 解出 的一个可行解 ，我们有

设

则

对 取模可以获得

结束。

lucas 定理

和范德蒙德卷积的证明很像

首先有

发现

所以

对比 即可。

有

约数和

怎么也是生成函数思想。

Day16

我咋阳了？？？？？？

问题分析

给定一棵树，节点编号为 到 的排列（即点权互异）。一条简单路径称为“完全非均衡路径”当且仅当：

  • 路径的两个端点不相同。
  • 路径上的点权最大值和最小值都出现在路径的端点上。

要求计算树中完全非均衡路径的数量。

解决思路

使用点分治（Centroid Decomposition）在 时间复杂度内解决该问题。点分治的核心思想是选取树的重心作为根节点，处理经过重心的路径，然后递归处理子树。关键点在于高效统计经过当前重心的路径中满足条件的路径数量。

路径条件转化

对于路径 （），设 , 。路径满足完全非均衡的条件等价于：

  • 是路径上的最小值， 是路径上的最大值。
  • 路径上所有节点的权值均在 之间。

点分治框架

  1. 选取重心：在当前连通块中找到重心 。
  2. 处理以 为端点的路径：对于每个邻居子树中的节点 ，检查路径 是否满足条件。
  3. 处理经过 且两端点均非 的路径：路径被 分割为 和 两部分（ 和 在不同子树）。需要统计满足以下条件的无序对 ：
    • 设 （反之类似），则：
      • 在 路径上： 是最小值，且所有点权值 。
      • 在 路径上： 是最大值，且所有点权值 。
  4. 递归：对 分割后的各子树递归处理。

高效统计路径对

对于经过 且两端点非 的路径，使用离线二维偏序查询：

  • 集合定义：
    • ：满足从 到 的路径上 是最小值的点 （即 ）。
    • ：满足从 到 的路径上 是最大值的点 （即 ）。
  • 事件处理：按子树顺序处理，对每个子树：
    • 查询：对当前子树的点 ：
      • 若 可作为较小端点（），则查询 中满足 且 的点 的数量。
      • 若 可作为较大端点（），则查询 中满足 且 的点 的数量。
    • 添加：将当前子树的点根据条件加入 或 。
  • 离线二维偏序：使用 Fenwick 树处理矩形查询：
    • 对 的查询：按 降序排序事件，查询满足 且 的点数（矩形 ）。
    • 对 的查询：按 升序排序事件，查询满足 且 的点数（矩形 ）。

算法步骤

  1. 全局初始化：设全局答案 。
  2. **点分治函数 solve(T)**：
    • 若树 为空，返回。
    • 在 中找重心 ，移除 得到子树 。
    • 对每个子树 ，DFS 计算从 到每个节点 的路径信息 （包括 和 ）。
  3. 处理以 为端点的路径：
    • 对每个节点 （在任意子树中，)：
      • 若 且 且 ，则 。
      • 若 且 且 ，则 。
  4. 处理两端点非 的路径：
    • 初始化事件列表 （用于集合 ） 和 （用于集合 ）。
    • 对每个子树 （按任意顺序）：
      • 查询（若 ）：对 中每个节点 ：
        • 若 ，向 添加查询事件 。
        • 若 ，向 添加查询事件 。
      • 添加：对 中每个节点 ：
        • 若 ，向 添加添加事件 。
        • 若 ，向 添加添加事件 。
    • **处理 **：
      • 按键值降序排序事件（添加事件键为 ，查询事件键为 ；同键值时添加优先）。
      • 用 Fenwick 树维护第二维 ，处理查询：对 ，求满足 且 的点数。
    • **处理 **：
      • 按键值升序排序事件（添加事件键为 ，查询事件键为 ；同键值时添加优先）。
      • 用 Fenwick 树维护第二维 ，处理查询：对 ，求满足 且 的点数。
  5. 递归：对每个子树 递归调用 solve(T_i)。

时间复杂度

  • 点分治深度：。
  • 每层点数和事件数：。
  • 事件排序：每层 ，总计 。
  • Fenwick 树操作：每个事件 ，总计 。
  • 总时间复杂度：。

空间复杂度

  • Fenwick 树每层 ，总深度 ，故总空间 。

代码实现（伪代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
global ans = 0

def find_centroid(T): 
    # 实现重心查找（略）

def solve(T):
    if T is empty: return
    root = find_centroid(T)
    remove root, get subtrees T1, T2, ..., Tk
    
    # 计算子树路径信息
    for each subtree Ti:
        for each node x in Ti (via DFS from root):
            min_x = min(min_parent, w[x])
            max_x = max(max_parent, w[x])
    
    # 处理以 root 为端点的路径
    for each node x in T (x != root):
        if w[root] < w[x] and min_x == w[root] and max_x == w[x]:
            ans += 1
        elif w[root] > w[x] and min_x == w[x] and max_x == w[root]:
            ans += 1
    
    events_A = []  # (type, w, val) for A: type=0 add, type=1 query
    events_B = []  # (type, w, val) for B: type=0 add, type=1 query
    
    # 初始化集合 A, B 为空
    for i from 1 to k:
        # 查询（对之前子树）
        if i > 1:
            for each y in Ti:
                if min_y == w[y]:
                    # 查询 B: (a, b) = (max_y, w[y])
                    events_B.append(('query', max_y, w[y]))
                if max_y == w[y]:
                    # 查询 A: (c, d) = (min_y, w[y])
                    events_A.append(('query', min_y, w[y]))
        # 添加当前子树点到集合
        for each y in Ti:
            if min_y == w[y]:
                events_A.append(('add', w[y], max_y))
            if max_y == w[y]:
                events_B.append(('add', w[y], min_y))
    
    # 处理 events_B（按 w 降序，添加优先）
    sort events_B by key: for add event, key = w; for query event, key = a; descending; for same key, add first.
    fenw_B = FenwickTree(size=n)  # 维护 min_z 维度
    for event in events_B:
        if event.type == 'add':
            w_val, min_z = event.w, event.val
            fenw_B.update(min_z, 1)
        else:  # query
            a, b = event.w, event.val
            count = fenw_B.query_range(b, n)  # [b, n]
            ans += count
    
    # 处理 events_A（按 w 升序，添加优先）
    sort events_A by key: for add event, key = w; for query event, key = c; ascending; for same key, add first.
    fenw_A = FenwickTree(size=n)  # 维护 max_z 维度
    for event in events_A:
        if event.type == 'add':
            w_val, max_z = event.w, event.val
            fenw_A.update(max_z, 1)
        else:  # query
            c, d = event.w, event.val
            count = fenw_A.query_range(1, d)  # [1, d]
            ans += count
    
    # 递归处理子树
    for each Ti:
        solve(Ti)

# 主函数
def main():
    build tree T
    solve(T)
    output ans

说明

  • Fenwick 树：用于高效处理二维偏序查询（单点更新、区间求和）。
  • 事件排序：确保在处理查询时，所有相关的添加事件已处理。
  • 去重：每条路径在点分治中仅被其深度最小的重心处理一次。
  • 正确性：通过离线事件处理，确保统计所有满足条件的路径对。

该算法在 时间内高效解决问题，适用于 较大的场景（如 ）。

  • Title: 2025 Summer MX
  • Author: rainbow-auto
  • Created at : 2025-07-14 22:55:16
  • Updated at : 2025-09-14 11:19:43
  • Link: https://rainbow-auto.github.io/2025/07/14/2025-Summer-MX/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
2025 Summer MX
  1. Day 1
    1. T1
    2. T2
    3. T3
    4. T4
    5. T5
    6. T6
  2. Day 2
    1. 鲜花
    2. 一言
    3. 扫描线
    4. 线段树合并
    5. 可持久化线段树
    6. 标记永久化
    7. 线段树上二分
    8. 猫树
    9. 线段树分治
    10. seg-beats
    11. 扩展域并查集判二分图
  3. Day3
    1. 鲜花
    2. Tarjan
    3. 2-SAT
    4. 二分图最大匹配
    5. 网络流建模技巧
    6. König 定理
    7. 二分图博弈
    8. 联通图容斥
    9. 度数序列
    10. Hall 定理
    11. 可达性
    12. Brovuka
    13. 耳分解
    14. P4581 [BJOI2014] 想法
  4. Day4
    1. 赛时
    2. T3
    3. T4
  5. Day5
    1. 树的重心
    2. 长链剖分
    3. 天天爱跑步
    4. [LNOI2014] LCA
    5. 树上背包
    6. [FJOI2014] 树的重心
    7. 单调栈
    8. 欧拉序求 lca
    9. 点分治
    10. 边分治
    11. 树上的树
  6. Day6
    1. 赛时
  7. Day7
    1. ACAM
    2. 01-trie
  8. Day8
    1. T2
    2. T3
  9. Day9
    1. CF79D Password
    2. P5309 [Ynoi2011] 初始化
  10. Day10
    1. 前置数学基础
    2. 定理1：Maschke定理的完整证明
    3. 推论：群代数维数公式
    4. Fourier变换与复杂度分析
    5. 快速 Fourier 变换（FFT）的递归结构
    6. Lev定理与复杂度上界
    7. 循环群 FFT：标准 FFT 的由来
    8. 总结：从群表示到实际算法
  11. Day11
    1. Sugoroku2
    2. ?
    3. [ABC182F] Valid payments
  12. Day12
    1. T2
    2. T3
  13. Day13
    1. P8110 [Cnoi2021] 矩阵
    2. P3193 [HNOI2008] GT考试
    3. 高斯消元
    4. 线性基
  14. Day14
    1. T1
    2. T2
    3. T3
  15. Day15
    1. exgcd
    2. excrt
    3. lucas 定理
    4. 约数和
  16. Day16
    1. 问题分析
    2. 解决思路
    3. 算法步骤
    4. 时间复杂度
    5. 空间复杂度
    6. 代码实现（伪代码）
    7. 说明