P16451 题解

qbf！ · 2026-05-15 23:22:32 · 题解

前言

本题是我投给今年集训队互测的题目，但是因为众所周知的原因没有过审，后来用于联考的省选模拟赛。

本题的原数据范围是 n\le 1.5\times 10^5,q\le 7.5\times 10^4，时间限制 4 s，空间限制 512 MB。但是因为存在一些复杂度劣于 std 的可以通过的算法，所以上传到 luogu 时开大了数据范围，且只造了三个测试点。std 在本地的用时为 40 s 左右，但是在 luogu 上的波动较大。

原数据范围如下：

对于子任务 1\sim 11，空间限制为 2 G，对于子任务 12，空间限制为 512 MB。

题解

标题含义：range virtual tree modify path query。

假设 n,q 同阶。

算法一

暴力，时间复杂度 \mathcal O(n^2)。

可以通过子任务 1，期望得分 5 分。

算法二

我们用如下方式计算虚树边权和：将所有点按 DFS 序排序后，把所有点到根的路径加上 v，再将所有相邻（包含第一个点与最后一个点之间的） LCA 到根的路径减去 v。

使用树状数组实现路径加单点查，时间复杂度 \mathcal O(\sum (r-l)\log n+n\log n)。

可以通过子任务 1\sim 2，期望得分 15 分。

算法三（所有查询在修改之后）

先考虑一个经典问题：每次将 f([l,r]) 加上 v，求最后每个点的点权。

我们将 f([l,r]) 对 x 的贡献看作：

• 若 [l,r] 中存在点在 x 子树内，则贡献 +v。
• 若 [l,r] 中所有点都在 x 子树内，且 x 不是 [l,r] 的 LCA，则贡献 -v。

满足第二种情况的 x 显然是一条从 LCA 的父亲到根的路径，这部分是平凡的，只需考虑如何处理第一种情况。

考虑启发式合并，这样只会有 \mathcal O(n\log n) 次对连续段的修改，每次修改时相当于查询一个矩形区域内的数的和，这可以离线下来然后扫描线。

时间复杂度 \mathcal O(n\log^2n)。

结合算法二，可以通过子任务 1\sim 3，期望得分 30 分。

算法四（保证不存在操作三、离线）

与正解无关。

先序列分块，对于一次修改 [l,r]，我们先将整块 [L,R] 的贡献加上 v，其中 L\le l\le r\le R，然后再减去从 [L,R] 变成 [l,r] 的贡献差。

考虑对每个 [L,R] 维护一个链表，然后删去左右的散点，每删一次就会产生一次从某个点到根的路径加的操作。

总共会产生 \mathcal O(n\sqrt n) 次路径加操作，但只有 \mathcal O(n) 次查询，使用 \mathcal O(1)-\mathcal O(\sqrt n) 的分块平衡即可。

接下来考虑如何计算 [L,R] 的贡献，我们沿用算法三的做法，[L,R] 对一个点 x 产生贡献当且仅当存在 [L,R] 中的某个点在 x 的子树内。

于是我们对每个点 x 维护出哪些块中存在点在其子树内，查询时我们枚举 r 然后计算所有 R=r 对 x 的贡献。

此时容易发现合法的 L 是一段前缀，于是问题等价于 \mathcal O(n) 次单点修改和 \mathcal O(n\sqrt n) 次查询前缀和，注意到整块的数量是 \mathcal O(\sqrt n) 级别，因此暴力维护前缀和即可做到 \mathcal O(n\sqrt n)。

时空复杂度 \mathcal O(n\sqrt n)。

结合算法二、三，可以通过子任务 1\sim 5，期望得分 55 分。

算法五（保证不存在操作三）

考虑每 \mathcal O(\sqrt n) 重构一次，利用​算法三，每次重构时等价于 \mathcal O(\sqrt n) 次单点加和 \mathcal O(n\log n) 次矩形查询，我们 \mathcal O(\sqrt n)-\mathcal O(1) 平衡一下即可。

散块的查询需要用可持久化线段树合并预处理每个点的子树信息，时间复杂度 \mathcal O(n\sqrt n\log n)，空间复杂度 \mathcal O(n\log n)。

可以通过子任务 1\sim 4,6，期望得分 55 分。

算法六（保证不存在操作三）

与正解无关。

考虑设一个阈值 B，对于 r-l\le B 的部分，我们沿用算法二，考虑将所有点按 DFS 序排序（可以预处理所有左端点为 B 的倍数，长度为 2B 的数组排序后的结果），将问题转化为 \mathcal O(nB) 次树链加和 \mathcal O(n) 次单点查，可以用 \mathcal O(1)-\mathcal O(\sqrt n) 的分块平衡至 \mathcal O(n(B+\sqrt n))。

对于 r-l>B 的部分，每个点 x 我们只保留长度 >B 的连续段（下文称为 \lceil有效连续段\rfloor），则每个点只有 \mathcal O(\dfrac nB) 个有效连续段，可以用启发式合并求出每个点的所有有效连续段。

这样问题等价于 \mathcal O(n) 次单点修改和 \mathcal O(\dfrac{n^2}B) 次矩形查询（即查询所有被有效连续段包含的修改的权值之和），使用二维分块（具体的，考虑建立一棵叉数为 n^{0.25} 的二维线段树）即可做到 \mathcal O(\sqrt n) 修改 \mathcal O(1) 查询，注意每次修改会带来 \mathcal O(\sqrt n) 的空间代价。

时间复杂度 \mathcal O(n\sqrt n+nB+\dfrac{n^2}B)，空间复杂度 \mathcal O(n\sqrt n+\dfrac{n^2}B)。

取 B=\sqrt n 即可做到 \mathcal O(n\sqrt n) 的时空复杂度。

结合算法三，可以通过子任务 1\sim 7，期望得分 70 分。

算法七

考虑拓展算法五，散块查询时，我们相当于要求出 x 的深度最大的祖先 y，使得 y 子树内存在编号 \in[l,r] 的点 k。

我们发现 k 肯定是 [l,r] 中 DFS 序比 x 的大的点中 DFS 序最小的点，和 DFS 序比 x 的小中 DFS 序最大的点。

于是问题转化为求区间内小于一个数的最大值和区间内大于一个数的最小值，以前者为例，我们将数从小到大插入，用主席树维护区间 \max 即可。

这样查询就可以做到 \mathcal O(\log n)，总时间复杂度 \mathcal O(n\sqrt n\log n)，空间复杂度 \mathcal O(n\log n)。

可以通过子任务 1\sim 4,6,8,10，期望得分 75 分。

算法八

当 B 较小时，重构时我们可以用位运算在 \mathcal O(n) 时间复杂度内求出影响每个点的操作集合，然后再 \mathcal O(2^B) 预处理每个集合的总和即可。对于散块，我们使用算法七的做法。

时间复杂度 \mathcal O(\dfrac{n^2}B+nB\log n)，取 B=\log_2 n 即可做到 \mathcal O(\dfrac{n^2}{\log n}+n\log^2n) 的时间复杂度。

可以通过子任务 1\sim 4,6,8,10，期望得分 75 分，卡常大师有概率获得更高的分数（后来被实践证明有概率通过）。

算法九

我们用可持久化分块代替主席树，块内建 \mathcal O(n)-\mathcal O(1) RMQ 查询区间 \max，这样时间复杂度可以平衡到 \mathcal O(n\sqrt{n\log n})，空间复杂度 \mathcal O(n\sqrt n)。

可以通过子任务 1\sim 11，期望得分 99 分，把分块换成分块套分块可以将空间复杂度优化至 \mathcal O(n^{4/3})，卡常大师有概率通过。

算法十

考虑 top cluster 树分块，设块大小为 B，我们将查询分为以下两种：

• 簇路径上的点
• 不在簇路径上的点。

对于第一种，我们每个上下界点间的路径肯定是一段前缀加，为了找到这个位置，我们相当于是查询簇内编号在 [l,r] 内的点跳到簇路径上的最深的那个点。

我们对每个簇中的点按照编号排序，用 ST 表维护区间最大值，然后用分散层叠算法（其实离线可以不用分散层叠）将 [l,r] 定位，再在 ST 表上查询。

这部分时间复杂度 \mathcal O(\dfrac{n^2}B+nB+n\log n)，空间复杂度 \mathcal O(n\log n)。

对于第二部分，相当于要对簇内的一条链求出答案，我们从下往上，每次加入当前点的其他儿子，这样相当于 \mathcal O(B) 次矩形查询，可以用二维分块做到 \mathcal O(\sqrt n) 修改 \mathcal O(1) 查询。

注意由于要查找前驱后继，所以要维护一个链表，先倒着删一遍求出前驱后继。

取 B=\sqrt n 可以做到 \mathcal O(n\sqrt n) 的时空复杂度，可以通过子任务 1\sim 11，期望得分 99 分。

算法十一（空间单 log）

我们每 T=\mathcal O(\sqrt n\log n) 个操作重构一次，重构时套用算法三的做法，这里要做 \mathcal O(n\log n) 次矩形查询，但由于点数是 \mathcal O(T) 的，故我们使用 \mathcal O(\sqrt n)-\mathcal O(1) 的分块平衡即可。

时间复杂度 \mathcal O(n\sqrt n)，空间复杂度 \mathcal O(n\log n)。

可以通过子任务 1\sim 12，期望得分 100 分。

如果有更好的想法，欢迎和出题人交流。

致谢

感谢 @wind_boy、@small_cyt、@qczrz6v4nhp6u、@i_am_czj 在本题出题过程中提供的帮助。