Problems

· · 个人记录

edit。

:::info[严格来说这个也搬到了本地，但是这些还是有参考价值的]

CF559E Gerald and Path

老师布置杂题的时候做的这题，居然做出来了，不敢相信。

CF*3000，div 1，E 题

dp

最开始考虑记录 f_{i, (0/1)} 为前 i 个线段且第 i 个线段朝左（右）的最大覆盖。

发现这样状态简单但是转移十分困难。难点在我们不知道前 i - 1 个的朝向，如果要硬记就要状压，放弃吧。

我们发现我们实际关心的并不是前 i - 1 个的状态而是最靠右边的线段。

那么可以考虑改状态为 f_{i, j, (0 / 1)} 代表前 i 条线段中第 j 条线段最靠右且朝向左（右），并且第 i 条线段的朝向对于转移的影响不大所以直接不记。

先对所有线段按左端点排序。

刷表法。

考虑 f_{i, j, p} 能影响到哪些位置。枚举 k \in [i + 1, n]，l \in \{0, 1\}，沿途顺便计算最靠右的位置，记为 K, L。

那么 f_{i, j, p} 就能影响到 f_{k, K, L}。

我们发现，因为我们排过序，所以 a_K \le a_k，又因为 a_K + L \times l_K 最大，所以 a_k + d \times l_k 到 a_K + L \times l_K 的区域是连续的（d 是现在对于 k 枚举的方向）。

再来看从 a_j + p \times l_j 到 a_k + d \times l_k 的贡献，这个值最大为 l_k，那么贡献为 \min(l_k, (a_k + d \times l_k) - (a_j + p \times l_j))。

f_{i, j, p} + (a_K + L \times l_K) - (a_k + d \times l_k) + \min(l_k, (a_k + d \times l_k) - (a_j + p \times l_j)) \to f_{k, K, L}

注意它的值域是 [-10^8, 10^8] 而不是 [0, 10^8]，所以最小值不要设置成 0。

P7738 [NOI2021] 量子通信 \dagger

cute，很难想象我能想出来。

题目大意：给出 n 个随机生成的 \textbf {256} 位 01 串，q 次询问，每次给定一个不随机生成的 {256} 位 01 串，询问是否有一个串与询问串的汉明距离不超过 k。

比较乱搞，不知道是不是正解。

首先，如果询问串也随机生成（即 16,17,18 测试点），那么询问大概率都是 0，因为存在汉明距离不超过 k 的概率极低，这是显然的。

观察到 k \le 15，我们可以考虑依靠鸽笼原理分块。将 256 位 01 串分成 16 \times 16 的形式，就变成了 2^{16} 进制下的 16 位数。

根据鸽笼原理，满足汉明距离不超过 15 的两个 01 串一定在 2^{16} 进制下有一位相同。

考虑枚举第 i 位相同，此时待选的 01 串个数就是 \left\lceil\frac{n}{2^{16}}\right\rceil = \left\lceil \frac{4 \times 10^5}{2^{16}} \right\rceil = 7，直接暴力判断汉明距离即可。

具体实现方面，每个 01 串都可以用一个 256 位的 bitset 存储，查找待选 01 串就用 vector 解决，不用 map，少一个 \log。

时间复杂度（差不多是）：

\mathcal{O}\left(\frac{m \times 16 \times \frac{n}{L} \times 16}{\omega} \right) = \mathcal{O}\left(\frac{nm}{\omega \times L} \right) ~~ \text{or} ~~ \mathcal{O}\left(\frac{nm}{L} \right)

tips：我两次写了一下午的代码忘存关机的时候清掉了，所以没有代码，咱就当它过了吧。

P3968 [TJOI2014] 电源插排 \dagger

题目大意：每人每次会从剩余最大的空位连续段中取中间位置使用，单修，每次求 l 到 r 中有多少个使用过。

set

阿 Q 的停车场加强版。

类似 ODT 的思想，用 set 维护长的空位连续段，每次取最长的并将其长度对半，分成两个重新塞回 set 里面，不过需要同时维护两个不同排序依据的 set，分别是连续段长度和连续段位置。

至于询问，没想到 set 的方法，就离线下来上树状数组暴力维护，需要离散化但问题不大。

代码没写，但应该不难。

upd（20251014）：其实这个做法挺难写的，细节很多，但其他数据结构做法好像都更难写。

时间复杂度 \mathcal {O} (q \log q) 或 \mathcal{O}(q \log n)。

P12639 / B3426 [UOI 2020] Topological Sorting of a Tree

（追随原神）

DP、组合

计数题就很不会，听 jzp 讲之后勉强懂了。

题目大意：给一棵树，需要给所有点填入一个排列，使得每条边给的大小关系都得到满足，求方案数。

这种题除了 DP 我也考虑不到什么其它解法。

记 f_{u, i} 表示在 u 的前 j 个子树中，u 的排名为 i 的方案数，注意状态中是 u 的排名为 i 而非 u 的取值。

对于每一个儿子 v，我们需要思考的就是如何从 f_{v, j} 转移到 f_{u, i}。考虑枚举 i \in \left[1, s_u\right]、j \in \left[1, s_v\right] 其中 s 数组代表子树大小，这里 s_v 不算在 s_u 里。

以 u,v 间的边边权为 < 为例。直接转移不好做，考虑再枚举一维 k \in [0, j - 1] 代表 v 前面的 j - 1 个数中有 k 个排名在 u 前面。那么转移就变成 f_{u, i} 和 f_{v, j} 一起转移到 f_{u, i + k}。接下考虑计算方案数，u 前面有 i + k - 1 个数，其中 k 个在 v 的子树中，那么方案数为 \binom{i + k - 1}{k}。同理 i 之后有 s_u - i + s_v - k 个数，其中 s_v - k 个在 v 的子树中，所以有方案数 \binom{s_u - i + s_v - k}{s_v - k}。

得出转移方程：

f_{u, i + k} = \sum_{i = 1} ^ {s_u} \sum_{j = 1} ^ {s_v}\sum_{k = 0} ^ {j - 1} f_{u, i} \times f_{v, j} \times \binom{i + k - 1}{k}\binom{s_u - i + s_v - k}{s_v - k}

然而这样时间复杂度为 \mathcal{O}\left(n^3\right)，需要优化。

观察到 j 这一维所涉变量只有 f_{v, j}，所以考虑把 j 放到最里面并把 f_{v, j} 提出来。

\begin{align*} f_{u, i + k} &= \sum_{i = 1} ^ {s_u}\sum_{k = 0} ^ {s_v - 1 } \sum_{j = k + 1} ^ {s_v}f_{u, i} \times f_{v, j} \times \binom{i + k - 1}{k}\binom{s_u - i + s_v - k}{s_v - k}\\ &= \sum_{i = 1} ^ {s_u}\sum_{k = 0} ^ {s_v - 1 } \left( \sum_{j = k + 1} ^ {s_v} f_{v, j} \right)f_{u, i} \times \binom{i + k - 1}{k}\binom{s_u - i + s_v - k}{s_v - k} \end{align*}

中间那一坨前缀和可以解决。

边权为 > 的同理。

\begin{align*} f_{u, i + k} &= \sum_{i = 1} ^ {s_u} \sum_{j = 1} ^ {s_v}\sum_{k = j} ^ {s_v} f_{u, i} \times f_{v, j} \times \binom{i + k - 1}{k}\binom{s_u - i + s_v - k}{s_v - k}\\ &= \sum_{i = 1} ^ {s_u}\sum_{k = 1} ^ {s_v } \left( \sum_{j = 1} ^ {k} f_{v, j} \right)f_{u, i} \times \binom{i + k - 1}{k}\binom{s_u - i + s_v - k}{s_v - k} \end{align*}

值得注意的是状态定义时我们默认滚掉了一维（即表示在 u 的前 j 个子树中这一维），故方程中的 f_{u, i} 应在转移前复制到一个新数组 g 中进行转移。

时间复杂度 \mathcal{O}\left(n^2\right)，足以通过此题。

B3642 「NOIP模拟」战斗

题目大意：n 个人，每个人有能力值 a，每次随机选择相邻两个人并淘汰一个人，i 与 i+1 中 i 留下的概率是 \frac{a_i}{a_i + a_{i + 1}}。求第 k 人最终剩下的概率，n \le 500。

考场只会 n^5，请教 gtx 后会了。

区间 dp

每次选择相邻的两个数，直接 dp 非常难做，考虑区间 dp。

记 f_{l, r, x} 为 [l, r] 中决斗中 x 胜出的概率。考虑如何转移。

发现需要枚举最后一次决斗是 x 与 y，并在 x 到 y 中枚举出一个分界点 i，转移：

f_{l, r, x} = \frac{\sum_{y > x} \sum _{k = x}^{y-1}f_{l, k, x} \times f_{k + 1, r, y} \times \frac{a_x}{a_x + a_y}}{r-l}

（注：因篇幅有限，所以上述转移方程只写了 y > x 的情况，y<x 可以自行推导，后面最终方程会写上）

思考发现状态已经达到 n^3 级别，不可能通过优化转移使得复杂度到达 n^3，只能考虑优化状态。

我们发现原来的 $f_{l, r, x}$ 本质上就是后来的 $f_{l, x, 1} \times f_{x, r, 0}$，因为 $x$ 必然会跟 $[l, x - 1]$ 和 $[x + 1, r]$ 的胜者各打一次，胜利概率分别为 $f_{l, x, 1}$ 和 $f_{x, r, 0}$，又概率相互独立，所以相乘即是结果，最终答案为 $f_{1, k, 1} \times f_{k, n, 0}$。 那么修改转移方程（令 $x$ 为胜者，取 $l$ 或 $r$）： $$ f_{l, r, 0/1} = \frac{\sum_{y > x} \sum _{k = x}^{y-1}f_{l, x, 1} \times f_{x, k, 0} \times f_{k + 1, y, 1} \times f_{y, r, 0} \times \frac{a_x}{a_x + a_y}}{r-l} $$ 复杂度就非常神奇地变成了 $n^4$。如何优化。 观察到分数线上面部分 $f_{l, x, 1}$、$f_{y, r, 0}$、$\frac{a_x}{a_x + a_y}$ 不含有 $k$，提出来。 $$ f_{l, r, 0/1} = \frac{\sum_{y > x} f_{l, x, 1} \times f_{y, r, 0} \times \frac{a_x}{a_x + a_y} \times \sum _{k = x}^{y-1}f_{x, k, 0} \times f_{k + 1, y, 1}}{r-l} $$ 我们发现 $\sum _{k = x}^{y-1}f_{x, k, 0} \times f_{k + 1, y, 1}$ 可以完美地解释为 $[x, y]$ 决斗并只剩下 $x$ 和 $y$ 的概率，而这个东西在整个方程中重复计算了 $\mathcal {O}(n)$ 次，所以可以将其改为 $g_{x, y}$，并在每次 $l,r$ 确定的时候计算 $g_{l, r}$，注意必须在计算 $f_{l, r, 0/1}$ 之前计算 $g$ 因为有可能 $f$ 计算过程中需要用到 $g$。 $$ f_{l, r, 0/1} = \frac{\sum_{y > x} f_{l, x, 1} \times f_{y, r, 0} \times \frac{a_x}{a_x + a_y} \times g_{x, y} + \sum_{y < x} f_{l, y, 1} \times f_{x, r, 0} \times \frac{a_x}{a_x + a_y} \times g_{y, x}}{r-l} $$ 时间复杂度 $\mathcal{O}\left(n^3\right)$，足以通过此题。 ### B3500 「NOIP模拟」数星星 > 题目大意：给一棵 $n$ 个结点的树，$m$ 条路径，每次询问 $[l, r]$ 区间内的路径并起来的点权和。 赛时看错题了，赛后 $1$s 就想出来了吗的。 > 树剖、ODT、树状数组 首先不带修区间询问还不强制在线可以直接考虑离线扫描线。 树上问题直接树剖，每次给一条链上的所有点打上区间覆盖的时间戳，仅打过前 $r$ 条路径的标记中，所有时间戳 $\ge l$ 的点就是存在于 $[l,r]$ 路径并集上的点。 区间覆盖直接 ODT，统计每个时间戳的结点的点权和直接开一个值域树状数组记录前缀和。值域 $10^9$，但是没事，可以离散化。 思考为什么用 ODT 复杂度正确，因为所有的查询和修改是同阶并同样的。 代码一点都不难写。时间复杂度 $\mathcal{O}\left(n \log ^ 2 n\right)$，空间 $\mathcal{O}(n)$，常数不是很大。 然后想了一下如果强制在线怎么做。 既然是数据结构，那就数据结构到底吧！ 因为前 $r$ 个路径和前 $r + 1$ 个路径建出来的 ODT 区别不大直接把 ODT 可持久化（好像因为复杂度均摊所以没有，写一个可持久化平衡树也行），值域树状数组改成主席树，直接记录每个 $r$ 对应的所有 $l$ 下标，查询的时候直接调用。时间 $\mathcal{O}\left(n \log ^ 2 n\right)$，空间 $\mathcal{O}(n \log n)$，常数极大。 还很难写，狗都不写好吧。 ### P8156 / B3654 「PMOI-5」奇怪的方程 > 题目大意：给一个 $n \times n$ 的矩阵 $A$，有 $m$ 对形如 $A_{x_i, y_i} = z_i$ 的条件，求构造一组满足所有条件且 $\sum_{j = 1} ^ {n} A_{i, j} = a_i$、$\sum_{i = 1} ^ {n} A_{i, j} = b_j$ 的矩阵。 网格图建图 trick 不会。 > 构造、Ad-hoc 首先，显然如果 $\sum a \ne \sum b$，则无解。 $m$ 个条件可以转化为 $A_{x_i, y_i}$ 不能填入数，同时将 $a_{x_i}$ 和 $b_{y_i}$ 减去 $z_i$。 如图，红蓝两个分别是空闲可以填入的格子；事实上，红蓝两个地方可以分开构造，两者相互独立。 ![](k054y698.webp) 考虑对于每一个可以填入的格子 $A_{i, j}$，行 $i$ 向列 $j$ 连边，即 $i$ 向 $j + n$ 连边。 只需要对于所有建图后的连通块进行构造即可。 显然，原图的边的个数是 $\mathcal{O}(n^2)$ 的，那么进行构造的复杂度至少就是 $\mathcal{O}(n^2)$。 然而，我们并不需要保留所有的边，只需要对所有连通块的一棵生成树构造即可。 考虑一颗生成树的构造顺序，从叶子结点往上一一构造（否则涉及的量很多），每次构造都将 $A_{i, j}$ 赋值为 $a_i$ 或 $b_j$，然后 $a_i$ 和 $b_j$ 减去 $A_{i, j}$。由于 $\sum a = \sum b$ 所以根节点的值也是正确的，不会自相矛盾。 时间复杂度 $\mathcal{O}(Tn^2)$，十分可过。 ### B3662 「NOIP模拟」艺术家 > 题目大意：给 $m$ 个区间 $\left[l_i, r_i\right]$，任意两个区间要么互相包含要么相离；每个位置有颜色，$q$ 次单点修改，求每个区间最早的区间内所有颜色互不相同的时间戳。区间两两不同，$1 \le n,m,q \le 5 \times 10^5$。 这个数据范围很像分块嘛www。 > 建图、线段树、单调栈 首先任意两个区间要么相含要么相离，则最后线段一定会构成一个树（森林）状结构，我们用单调栈考虑建出这棵树。 由于区间两两不同，所以父节点 $u$ 位置上的答案一定会大于子节点 $v$ 的答案。 按顺序处理 $q$ 次修改，那么每次我们需要考虑的有且仅有当前树仅剩的叶子结点。 由于是叶子结点，所以两两的交集肯定为空，所以覆盖到单点查询的线段有且仅有一条，从 set 中拿出来直接处理，如果已经两两不同就可以直接计入答案然后把这个叶子删掉。 然而删掉一个叶子之后有可能影响到祖先链的所有区间，所以还需要递归处理，由于每一个区间之会被删除一次，所以均摊是 $\mathcal{O}(q \log n)$（瓶颈是 set 复杂度）的。 如何判断是否两两不同？考虑用线段树，记 $l_i = j$ 为 $\max \left\{ 1 \le j \lt i, a_j = a_i \right\}$，那么 $L$ 到 $R$ 两两不同当且仅当 $\max_{i = L} ^ {R} l_i \lt L$。 时间复杂度，贪心排序后建树复杂度为 $\mathcal{O}(m \log m + n \log n + m \log n)$，处理每询问的复杂度是 $\mathcal{O}(q\log n + q\log m + n \log n + n \log m)$。 综述，复杂度为 $\mathcal{O}(n \log n)$（设 $n,m,q$ 同阶）。 具体实现有点难写。 ### B2353 「NOIP模拟」文明 > 题目大意：给一棵节点的树，$q$ 个询问，每次给 $k_i$ 个已经染好互不相同颜色节点，每秒会向周围没有颜色的点扩散，求 $10^{100}$ 秒后第一种颜色有多少个。 赛时先做的 T2，磕了一会看了眼这题，结果秒了，但鉴于 T2 调太久，所以没调完。并且赛时代码仅修改两个字符可以通过。 > 线段树、倍增 设选择节点序列为 $a$，$u = a_1$。 我们不关心 $a$ 序列中除了 $u$ 以外的所有节点互相之间的关系，所以仅考虑 $u$ 与 $v \in a_{2, 3, \cdots, k_i}$ 的关系。 我们发现，扩散相遇的位置即 $u$ 和 $v$ 的道路中点更偏 $v$ 的位置。 那么删掉所有扩散相遇的临界那条边，剩下的若干连通块就是最终结果了。 我们可以通过倍增树上 $k$ 级祖先来维护每个 $v$ 和 $u$ 的中间那条边 $w \to w^{\prime}$，设 $w$ 的深度更浅。 在 $\text{dfs}$ 序上，我们用 $1$ 代表属于 $u$ 的连通块，$0$ 代表不属于，则最开始整个序列全部赋值为 $1$。 考虑用线段树维护，分类讨论边的两种情况： - 即 $w$ 在 $u$ 的祖先链上，那么断掉之后 $w$ 的父亲方向与除 $w^{\prime}$ 以外所有儿子都将与 $u$ 属于不同连通块。即只保留 $w^{\prime}$ 的子树。 对于这一类节点，我们直接记录下深度最深的这一类节点并在最后查询的时候只在线段树上查这部分子树的和即可。 - 否则，断掉后只会将 $w^{\prime}$ 的子树全部脱离 $u$ 的连通块，即将 $w^{\prime}$ 的子树置为 $0$。 由于一棵子树的 $\text{dfs}$ 序是连续的，所以改起来就是区间覆盖、区间和。 每次求完都全部置回 $1$，方便下一次使用。 还有不用线段树的归并做法，不会，好高级。 ### P10241 [THUSC 2021] 白兰地厅的西瓜 > 题目大意：求不定点最长树上 LIS。 困难题。 > 线段树合并。 将答案拆成两部分，$u$ 子树到 $u$ 的最长上升子序列，$u$ 到 $u$ 子树的最长上升子序列。记 $f_u, g_u$ 分别为包含 $u$ 的上述两种情况。 转移很简单。 我们发现转移本质是一个值域区间 dp 值取 $\max$，线段树维护。子树的话就用线段树合并二路归并。 然而有可能出现 $u$ 点不选的情况，这种情况在合并的时候就统计了即可。 ### CF273D Dima and Figure 跟出题人对上脑电波了。![](https://www.emojiall.com/images/60/qq/1f44d.gif) > 题目大意：一个 $n \times m$ 的矩阵，你可以将部分格子涂黑，一个涂黑方案合法当且仅当黑部分联通且任意两黑点都存在一条最短路上全是黑点。 > dp。 我们考虑构造方案的双射，我们发现原方案合法当且仅当每一行的涂黑部分都是连续的且左右边界都不超过单峰。 根据这个双射，我们可以分别对于左右边界的升、降部分进行 dp。 具体的，记 $f_{i, l, r, 0/1, 0/1}$ 为仅填入连续 $i$ 行的情况下，被填入的第 $i$ 行的涂黑部分是 $[l, r]$、左右分别还是否可以向外的方案（即是否已经存在一个峰）的情况下的方案数。 转移比较简单吧，考虑一下左右是否能扩展就行。然后把 $i$ 滚掉。然而复杂度是 $\mathcal{O}(n^5)$，过不了。 考虑前缀和思想转移（完全背包），对于每一轮 $i$，每次只转移相邻的两种状态，这样也能转移成功。复杂度很优秀，$\mathcal{O}(n^3)$。 ### CF1372E Omkar and Last Floor 事实证明我没有听过 jzp 讲课？ > 贪心、区间 dp。 题目贡献为 $\sum x^2$ 的形式，考虑贪心，因为 $(x + y) ^ 2 > x ^ 2 + y ^ 2$ 恒成立。故贪心使所有的 $1$ 挤到一起是最优的。于是我们需要考虑的就是「挤」的优先级。 区间 dp，设 $f_{l, r}$ 为 $[l, r]$ 区间内的最大价值。 考虑枚举一个 $i \in [l, r]$ 作为一个「挤」的点，那么 $n$ 个区间中所有包含 $i$ 的区间都应该挤过来，贡献 $\left(\sum_{l \le L_j \le i \le R_j \le r} 1\right)^2$。接着分开处理 $[l, i - 1]$ 和 $[i + 1, r]$ 两个区间，即 $f_{l, i - 1} + f_{i + 1, r}$。 方程： $$ f_{l, r} = \sum_{l \le i \le r} f_{l, i - 1} + f_{i + 1, r} + \left(\sum_{l \le L_j \le i \le R_j \le r} 1\right)^2 $$ 好像可以优化，但是可过，时间复杂度 $\mathcal{O}(n^4)$。 实现上，记一个数组代表每个位置的所属区间，再记录每个区间的左右端点即可。 ### CF1990F Polygonal Segments 高深 ds 题，jzp 好像讲明白了。 > 题目大意：一个长度为 $n$ 的序列 $a$，单修，区查 $[l, r]$ 是否能构成一个 $r - l + 1$ 边形。 > 线段树、笛卡尔树（思想）。 首先，一堆数构成一个多边形的充要条件是 $2 \times \max a < \sum a$，事实上这个与非最大值是什么无关。而这其实是一棵笛卡尔树。 笛卡尔树好像不能优秀地可持久化，所以说我们先考虑静态暴力怎么做。 每次遍历到一个结点，看是否满足条件，如果是，该次查询的答案就是该结点的子树区间。否则，继续向左右子树递归。 接下来往哪个方向优化？我们可以思考一下性质。 我们正在遍历结点 $u$，说明结点 $u$ 本身是不合法的，也就是说 $2a_u \ge \sum_{v \in T_u} a_v$（记 $T_u$ 为 $u$ 的子树集合）。 进一步的，$\frac{\sum_{v \in T_u} a_v}{2} \le a_u$，也就是说，在不合法的结点往下递归时和至少减半，也就意味着遍历高度是 $\mathcal{O}(\log W)$ 级别的。 这是一种静态的处理方式，如何转为动态？ 我们可以不真的建立笛卡尔树，利用线段树辅助解决问题，pushup 就是以上过程，每次都查询一次最大值的值和下标，而处理最大值需要一个 $\mathcal{O}(\log n)$，因为我们递归时两棵子树都要递归，pushup 的复杂度是 $\mathcal{O}\left(2^{\log W} \log n\right) = \mathcal{O}(W \log n)$。 肉眼可见过不了，如何优化到只走一棵子树？ 我们发现，左右两个区间一定有一个被完全包含在了 pushup 合并的两个区间中，而这个区间已经在处理左右子树的答案时计算过了，故我们可以挑出这个区间并不选择它。pushup 时间复杂度变为 $\mathcal{O}(\log W \log n)$。 算上线段树本身的一个 $\log$，以及查询与建树的 $n$，总复杂度为 $\mathcal{O}(n \log ^ 2 n \log W)$。空间则是线性。 ### CF1131G Most Dangerous Shark 阴间输入。 > 题目大意：推萝莉，可以向左或向右推萝莉，每次推萝莉需要代价，求推倒所有萝莉的最小代价。 数据范围 $10^7$，因为输不下所以输入相当阴间，建议好好弄清楚。 现在我们得到了萝莉序列。用单调栈预处理出每个萝莉分别向左和向右分别最多能推倒到哪一个萝莉，记为 $L,R$ 数组。 dp，定义 $f_i$ 为推倒前 $i$ 个萝莉需要的最小代价。 两种情况，第一个是亲自推倒第 $i$ 个萝莉，并通过连锁反应中被推倒的萝莉推倒剩下的萝莉，即 $c_i + \min_{L_i \le j \le i} f_{j - 1}$。 第二种情况是前面有一个萝莉通过连锁反应推倒了第 $i$ 只萝莉，即 $\min_{j \le i \le R_j} \{f_{j - 1} + c_j\}$。 $$ f_{i} = \min\left(c_i + \min_{L_i \le j \le i} f_{j - 1}, \min_{j \le i \le R_j} \{f_{j - 1} + c_j\}\right) $$ 这个式子我用嘴巴想了一个带 $\log$ 的大常线段树做法，由于我们的数据范围不能带 $\log$，如果带 $\log$ 有能卡过的我请你抽烟。我们需要优化。 我们很容易发现 $f$ 数组肯定是不降的（读者自证不难），那么第一项可以直接转化成 $c_i + f_{L_i - 1}$。 如何优化第二项？有一个结论，任意两个 $[i, R_i]$ 与 $[j, R_j]$，要么包含，要么相离。 > 证明：假设存在一个 $j$ 使得 $i \lt j \le R_i \lt R_j$。 > > 由于 $i \le j \le R_i$，推倒萝莉 $i$ 时可以推倒 $j$，而推倒 $j$ 则会推倒 $R_j$，所以 $R_i \gt R_j$，然而这与原假设矛盾，故原假设不成立。 这个时候可以尝试优化。将包含关系看作父子关系，那么这些 $[i, R_i]$ 的区间可以看作一个森林。 根据我们的结论，$j \le i \le R_j$ 等价于 $j \le i \le R_i \le R_j$，在森林里表现为是 $[j, R_j]$ 区间的子树之一，这个东西可以用一次树上 dfs 预处理。 ### CF364D Ghd > 题目大意：给 $n$ 个数，求一个最大的数使得它是超过 $n / 2$ 个数的公约数。 > 随机化。 超过一半很像一个随机化。 每次随机一个位置 $x$，对其求出所有的因数，看这些因数同时为多少个数的因数，对于所有统计大于 $n / 2$ 的求一个最大值。 随即出来的 $x$ 每次不在要求的集合内的概率严格小于 $\frac{1}{2}$，那么随机 $15$ 次错误率就是 $\frac{1}{32768}$ 。 ### P14372 [JOISC 2018] 比太郎的聚会 / Bitaro's Party 根分。 > 题目大意：给一个 DAG，求每次给定顶点集 $S$ 与顶点 $T$，求起点 $s \notin S$ 且终点 $t = T$ 的路径中长度最长的长度为？ 注意到 $\sum|S| \le 10^5$，考虑根分。 - 若 $|S| \ge B$，这样的询问不会超过 $\frac{n}{B}$ 个，直接暴力计算，时间复杂度 $\mathcal{O}\left(\frac{n}{B}\right)$。 - 若 $|S| \lt B$，被禁用的点很少，也就是说我们可以对于每一个点预处理出能到达它的前 $B$ 长的路径，询问中直接调用即可。预处理时间复杂度 $\mathcal{O}(nB)$，询问复杂度 $\mathcal{O}(B)$。 貌似 $B$ 取 $\sqrt{n}$ 的 $\mathcal{O}(n ^ {3 / 2})$ 复杂度最优？反正实现好看一点不用带 $\log$。 考虑到空间问题，可稍稍下调块长。 ### CF1446D1 Frequency Problem (Easy Version) 一个只能过 easy ver 的 naive 做法。本来是看根分做的这题，结果发现了简单做法就给过了。 > 题目大意：一个长为 $n$ 的序列 $a$，求一个最长子段使得其有两个不同的众数。 jzp 曾经说过，区间众数的性质需要从全局众数那里推到。 而本题中的两个不同众数 $x$、$y$ 一定有一个是全局众数 $C$。 如何证明？假设存在最长的 $[l, r]$ 有 $x$、$y$ 两个众数，使得 $x \ne y \ne C$。因为 $C$ 是全局众数，则一定存在一个 $L \le l \le r \le R$ 的 $[L, R]$，满足 $C$ 的出现次数不小于 $x$、$y$，但这与 $[l, r]$ 最长矛盾，故原结论成立。 因为值域 $W = 100$，则可以直接枚举不是 $C$ 的众数 $x$。统计答案。 一个 trick 是将所有值为 $C$ 的设成 $1$、$x$ 设成 $-1$，其余设成 $0$，转化为求最长和为 $0$ 的子段。 如果有另一个数 $y$ 在该子段中出现次数更多又当如何？无妨，同样的道理，一定会存在一个区间包含该区间且 $C$ 的出现次数与 $y$ 相等，所以这样的区间就算计入答案也不会影响最终答案。 [back](https://www.luogu.com.cn/article/s4jiqvuu)。 ## jzp 的题，所以使用 jzp 评级法 ### $\color{purple}\blacksquare$ P5309 [Ynoi2011] 初始化 > 题目大意：修改，所有 $i \bmod x = y$ 的位置的 $a_i$ 全加上 $z$；查询，区间和。 这种 $i \bmod x = y$ 的即剩余系平衡，考虑平衡规划，设阈值为 $b$。先看修改。 - 若 $x \gt b$，则满足条件的 $i$ 有 $\mathcal{O}\left(\frac{n}{b}\right)$ 个，直接暴力改。时间复杂度 $\mathcal{O}\left(\frac{n}{b} \times p\right)$。 - 若 $x \le b$，需要更优秀的算法。我们发现它的优势是这样的 $x$ 只有 $b$ 种。不妨打表将计算过程放到询问里，记 $t_{x, y}$ 为对 $i \bmod x = y$ 的修改的 $z$ 值和。不过为了更快，记 $s_{x, y}$ 为 $t_{x, y}$ 的前缀和进行查询。时间复杂度 $\mathcal{O}(q + b)$。 其中 $p,q$ 是我们选用的一种数据结构的单修与区查的时间复杂度。 我们发现，在 $p = 1, q \le \sqrt{n}, b = \sqrt{n}$ 时复杂度最为优秀，为 $\mathcal{O}(n \sqrt{n})$。 而这种数据结构显然是分块。需要大力卡常。 ### $\color{red}\blacksquare$ CF1194F Crossword Expert > 题目大意：共 $n$ 个游戏，$T$ 秒，每个游戏有 $1 / 2$ 的概率花 $t_i$ 秒，$1 / 2$ 的概率花 $t_i + 1$ 秒，求完成的游戏个数期望。 无赖做法。 记 $s$ 为 $a$ 的前缀和。 期望的定义式是 $E = \sum _ {i = 0} ^ {n} iP_i$，可以考虑将它转化成 $E = \sum _ {i = 0} ^ {n} S_i$，其中 $S_i = \sum _ {j = i} ^ {n} P_j$ 即 $P$ 的后缀和。 $S_i$ 的组合意义为完成游戏个数不少于 $i$ 个的概率。其中总方案数是前 $i$ 个游戏的决策种类数即 $2^i$。合法方案数即选择不超过 $T - s_{i}$ 个游戏多花费一秒。即 $\sum_{j = 0} ^ {T - s_{i}} \binom{i}{j}$，二者相除即可。 $$ E = \sum_{i = 0} ^ {n} \frac{\displaystyle\sum_{j = 0} ^ {T - s_{i}} \binom{i}{j}}{2 ^ {i}} $$ 观察发现这是一个下指标求和，不会推式子咋办。 可以直接离线后莫队暴力跑。时间复杂度 $\mathcal{O}(n \sqrt{n})$。 ### $\color{purple}\blacksquare$ CF1790F Timofey and Black-White Tree wyb 亲传的 $\mathcal{O}( n \ln n )$ 做法。 > 题目大意：每次染黑一个点，求染黑后的两点间最短距离。 我不会平衡规划。 有一个神秘结论，在染黑了 $x$ 点之后的最短距离是 $\mathcal{O}\left(\frac{n}{x}\right)$。不会证明。 考虑一种暴力，枚举 LCA。记 $d_{u}$ 为 $u$ 的子树内的黑点到 $u$ 的最短距离。 每次染黑一个点 $v$ 后，枚举 $v$ 的 $i$ 级祖先 $w$，将 $d_w + i$ 作为值更新答案 $\text{ans}$。正确性显然，时间复杂度 $\mathcal{O}(n ^ 2)$。 考虑优化，由于在染色之前已经有最优解 $\text{ans}$，故 $i$ 的上界是 $\text{ans}$ 而非 $n$。根据我们之前提到的结论，复杂度为 $\mathcal{O}\left( \sum \frac{n}{i} \right) = \mathcal{O}(n \ln n)$。 跑得飞快，只用了 187ms，比 wyb 的 250ms 还快，你也来试试吧！ ### $\color{red}\blacksquare$ CF1032F Vasya and Maximum Matching jzp 讲的喵喵 dp 题。 > 题目大意：对一棵树求删边方案个数使得删完存在唯一最大匹配。 我们容易发现对于一棵树进行删边形成的结构是一个森林，即多棵树。那么可以分析一下一棵树存在唯一最大匹配的条件。 手玩一下样例再构造几种树会发现，每一个结点在最大匹配中必须恰好被一条边选择，否则可以与相邻的点进行交换这样匹配数量就不唯一。 当然还有一种可能是孤立点，即没有边的树。 我们的 dp 方式有眉目了，考虑记 $f_{u, 0/1/2}$ 为 $u$ 是单点 / 与儿子连边 / 与父亲连边时子树内部的删点方案数。 $f_{u, 0}$ 的转移较为简单： $$f_{u, 0} = \prod _ {v \in g_u} (f_{v, 1} + f_{v, 0})$$ $f_{u, 2}$ 次之，对于所有 $v$ 进行决策，若 $v$ 是孤立点则该边必须删掉，否则可删可不删，故 $f_{v, 1}$ 项要带一个 $2$ 的系数： $$f_{u, 2} = \prod _ {v \in g_u} (2 \cdot f_{v, 1} + f_{v, 0})$$ $f_{u, 1}$ 则是枚举向父亲连边的 $v$，除 $v$ 外剩余转移与 $f_{u, 2}$ 同理： $$f_{u, 1} = \sum _ {v \in g_u} f_{v, 2} \times \prod_{w \ne v} (2 \cdot f_{w, 1} + f_{w, 0})$$ 显然这个式子可以转化成全局积除以单点值，模数为质数，正确。 ### $\color{red}\blacksquare$ CF1819C The Fox and the Complete Tree Traversal > 题目大意：一棵树上每个点可以跳到离该点距离不超过 $2$ 的位置，问是否能不重不漏地跳完整棵树。 有一个神秘结论，这棵树可以跳完当且仅当这棵树的形态是一个链上挂着若干个单点。如何证明？ > **充分性**；即举出一种构造方法。可以考虑从左往右遍历链，奇数位置取该点，偶数位置取该点连向的所有边，然后再反着取一遍。可以证明每次取的两个点的距离不超过 $2$。 > > **必要性**；反证法，假设有一个点 $v$ 挂了一个并不是单点的子树，而其在链上的前一个点为 $u$，后一个点为 $v$。在第一次的遍历中要么从 $u$ 来要么从 $v$ 来，此时必会存在两个相邻的链上点被同一次遍历选到，故第二次遍历将会失败。无法成功故不存在这样的合法树。 事实上这个链挂单点的结构中的链一定是直径。所以说只需要写一个双 dfs 求直径即可。 ### $\color{red}\blacksquare$ CF1868C Travel Plan > 题目大意：一个 $n$ 个点的完全二叉树，求在所有点权值不超过 $m$ 的情况下，$\sum_{s} \sum_{t} d_{s, t}$ 的值，其中 $d_{s, t}$ 为路径最大值。$n \le 10^{18}, m \le 10^5

发现 m 较小，考虑枚举 d_{s, t} = k，则对于每一种 k 求出 \sum_{s}\sum_{t}[d_{s, t} = k] 即可。我们发现这个式子并不好求。但它的前缀和式子 \sum_{s}\sum_{t}[d_{s, t} \le k] 好求。即路径上所有点的点权都不大于 k 的路径个数。

路径个数可以枚举 lca 然后在 lca 处统计 dp。因为是完全二叉树所以任何子树大小相同的点子树形态也就相同，直接枚举子树大小即可。而子树大小至多有 \log n 种。

路径有关 dp，直接插头；记 f_{u, k} 为 u 子树内的路径，g_{u, k} 为 u 子树内到 u 的路径个数。

然后转移做完了 qwq。复杂度 \mathcal{O}(Tm\log n)

\color{red} \blacksquare CF1859E Maximum Monogonosity

题目大意：给两个长为 n 的序列 a, b，选择若涵个总长为 k 的区间，使得 \sum |b_l - a_r| + |a_l - b_r| 最大。n, k \le 3 \times 10^3

这种绝对值题不要想着去预处理贡献然后做，这种题很多都是拆绝对值做，本题也不例外。

考虑一种朴素 dp，记 f_{i, j} 为前 i 位中已经选取了总长位 j 的若干区间后的最大价值。

f_{i, j} = \max\left( f_{i - 1, j}, \max_{h = 1} ^ {j}f_{i - h, j - h} + |b_{i - h + 1} - a_i| + |a_{i - h + 1} - b_i| \right)

复杂度是 \mathcal{O}(n^2k)，不可过。考虑拆绝对值优化。

一个形如 |x| + |y| 的绝对值式子可以转化成 \max(x + y, x - y, -x + y, -x - y)，本题同理。而最终求的是最大值也就是说除最大值外三个是否参与计算事实上不重要。

\begin{align*} |b_i - a_j| + |b_j - a_i| &= \max\{(b_i - a_j + b_j - a_i, b_i - a_j - b_j + a_i, -b_i + a_j + b_j - a_i, -b_i + a_j - b_j + a_i\} \\ &= \max\{(b_i - a_i) + (b_j - a_j), (b_i + a_i) + (-b_j - a_i), (-b_i - a_i) + (b_j + a_j), (-b_i + a_i) + (-b_j + a_j)\} \end{align*}

这个可以直接拆成四种贡献并分开计算，记一个前缀 dp 值最大值即可，时间复杂度 \mathcal{O}(nk)，可过。

\color{red}\blacksquare CF1609F Interesting Sections

神秘卡常题。

题目大意：求一个序列的最大值与最小值的 popcount 相等的子区间数。n \le 10^6, a_i \le 10^{18}

扫描线枚举 $i$，我们需要求后缀最大值。考虑上单调栈，并用每一个元素以及它前面的所有元素为区间分组，此时一个区间内的所有元素为开头的后缀最值都是该区间的右端点。 直接开两棵线段树维护每个位置 $i$ 开头的后缀最值的 popcount 是否是 $p$。这两棵树只需要在单调栈出入栈的时候修改。复杂度 $\mathcal{O}(n \log n \log W)$，如果有能卡过的我给你磕一个。 加一个微不足道的优化，更新线段树前判一下当前区间的右端点的 popcount 是不是 $p$，由于每个数只会适配一个 $p$，所以总体下来线段树修改次数是 $\mathcal{O}(n)$ 的，故时间复杂度 $\mathcal{O}(n \log W + n \log n)$。 但是卡常。需要把线段树改成树状数组，并把单调栈改成 vector 再 reserve 一下才能卡过。 ### $\color{red}\blacksquare$ CF1887D Split > 题目大意：一个序列 $a$，多次查询 $a_l, a_{l + 1}, \cdots, a_r$ 是否能划分成左右两段使左段所有数都小于右段。 考虑枚举最大值 $x$，找到其在数组 $a$ 中的下标 $i$。即求 $i$ 作为左段最大值合法的 $[l, r]$ 有哪些。 由于 $x$ 是左段最大值，故找到 $i$ 之前第一个满足 $a_j > a_i$ 的 $j$ 不能在区间中，$j \lt l \le i$。 而右段的所有值必须大于 $x$，故找到 $i$ 之后第一个满足 $a_k > a_i$ 的 $k$，$k - 1$ 不能在右段中，$k \le r$。 同理找到 $k$ 之后第一个满足 $a_i > a_m$ 的 $m$，$m$ 不能在区间内，$r \lt m$。 $j, k, m$ 可以通过 set 维护预处理得出，问题变成二维数点，直接上树状数组即可。 ### $\color{red}\blacksquare$ CF1442C Graph Transpositions > 题目大意：一张边权为 $1$ 的有向图，可以花 $2^{k}$ 的代价反转所有边的方向，$k$ 为反转次数。求 $1 \rightarrow n$ 的最小代价。 简单题，但是乱搞做法。 直接上 bfs 硬搞，取模很麻烦，考虑反转的代价保留到最后再算。因为 $k > 20$ 基本上就肯定比剩余代价大了，故我们排序以反转次数为第一关键字。 记 $A_{u}$ 为到达结点 $u$ 所需的最少反转次数。显然若 $A_{u} > 20$ 则只需保留使其取到最小值的一条路径。$A_{u} \le 20$ 的情况就直接尽数保留了，想不出来其他的写法。 交上去 TLE on 13，咋办。 不咋办，卡个时就过了。 ### $\color{orange}\blacksquare$ P7710 [Ynoi2077] stdmxeypz 这辈子第一道橙是 Ynoi。。 > 题目大意：给你一棵边权为 $1$ 的有根树，每个点有初始为 $0$ 的点权值，需要支持两种操作：子树中所有与根的距离模 $x$ 等于 $y$ 的节点权值加 $z$、查询结点的权值。 jzp 在上面苦口婆心地讲 $\mathcal{O}\left(n \sqrt{ n \log n }\right)$ 的长剖做法，我在下面思考神秘分块 $\mathcal{O}\left(n \sqrt{n}\right)$ 做法，不是这不难吧。 参考 P5309，对 $x$ 根号分治，阈值为 $p$。对 dfs 序分块，块长为 $q$。 散块嘛，直接做好了，反正复杂度不会假掉的。 - $x > p$：记 $f_{i, j}$ 为第 $i$ 个块中所有深度为 $j$ 的点的标记。具体操作就是枚举所有符合 $w \bmod x = y$ 的深度 $w$，区间 $f_{[b_l, b_r], w}$ 全部加上 $z$，差分一下即可。 - $x \le p$：这一部分则相对比较好做。记 $g_{i, j, k}$ 为块 $i$ 中所有符合 $h \bmod j = k$ 的深度 $h$ 的标记。具体操作就是枚举 $d \in [b_l, b_r]$，对所有 $g_{d, x, y}$ 全部加上 $z$。 查询直接硬统计就好啦。 - 时间复杂度：$p = q = \sqrt{n}$，$\mathcal{O}\left(n \sqrt{n}\right)$。 - 空间复杂度：$\mathcal{O}\left(n \sqrt{n}\right)$。 ### $\color{red}\blacksquare$ P9067 [Ynoi Easy Round 2022] 虚空处刑 TEST_105 > 题目大意：同色连通块合并、查询极大同色连通块大小。 题解区学来的两只老哥的神秘做法。 记 $p_{u, col}$ 为 $u$ 结点所在同色连通块相邻的颜色为 $col$ 的结点。然后写了一下发现死了。 那咋办，看看题解；发现维护父亲会死，修改相邻为下方相邻。然后启发式合并一下。 还是做不了：） 暴力一点，再上一个并查集，正确性对了。 复杂度怎么是 $\mathcal{O}(n \log ^ 2 n)$，Ynoi 能过我吃欸咋过了？ ### $\color{red}\blacksquare$ CF1819C The Fox and the Complete Tree Traversal 一语点醒梦中人。 > 题目大意：一个网格图只保留值在 $[l, r]$ 的格子可以构成树形结构的 $(l, r)$ 对个数。 扫描线，枚举 $r$，维护一个最小的 $l$ 使得区间 $[l, r]$ 保留在图中是一棵树，记 $p_r = l$。不难发现 $p$ 具有单调性，故实现上我们用双指针 + LCT 维护。 点边容斥，树的判定是 $V - E = 1$（$V$ 是点数、$E$ 是边数）。而保留 $[l, r]$ 的所有点，有 $V = r - l + 1$，整理一下式子可以得到 $E + l = r$。 类似经典题 [CF526F](https://www.luogu.com.cn/problem/CF526F)，LCT 维护的是生成树，所以 $E_{\max} + l = r$，而在 $l = r$ 的时候肯定可以取到这个 $\max$，所以说我们只需要再次扫描线并动态统计 $E + l$ 的最大值及其个数即可。而这个可以上线段树。 令 $S = nm$，时间复杂度 $\mathcal{O}(S \log S)$，足以通过此题。 ### $\color{red}\blacksquare$ CF1732E Location 这是我第三次写这篇题解，前两次没保存炸掉了 > 题目大意：两个序列 $a, b$，你需要支持区间覆盖 $a$，区间查询 $\min \frac{\text{lcm}(a_i, b_i)}{\gcd(a_i, b_i)}$。 这个题 ODT 应该不是很好做，一个连续段每个位置的答案都不养不好处理。当然我也不确定。 鄙人不会除了分块的其他东西，所以我们直接上序列分块。 查询的时候散块直接暴力查，整块预处理，记 $g_i$ 为第 $i$ 块的答案。修改的时候散块仍然暴力，不过整块不是很好做。考虑记区间覆盖标记 $t_i$。然后你发现似乎还是不是很好做，$t$ 与 $g$ 的处理没法在 $\log$ 的时间内解决，咋办。 不咋办，直接暴力。记 $m_{d, i}$ 为第 $i$ 块中所有 $d$ 的倍数 $b_j$ 的 $\frac{b_j}{d}$ 的最小值。整块修改的时候我们可以枚举 $x$ 的所有因数，更新 $g_i = \min _ {p | x}m_{d, i} \times \frac{x}{p}$。 时间复杂度：$\mathcal{O}(n\sqrt{n}\log n + q\sqrt{n}\tau(V))$，其中 $\tau(V)$ 为 $V$ 的因数个数。 理论上 $\tau(V) \sim n ^ {1 / 3}$，实测 $\max \tau (x)$ 不超过 $100$，无伤大雅。 实现上，可以搞一个 $\mathcal{O}(1)$ 的 $\gcd$。具体的，上值域分块。 $5 \times 10^4$ 以内的任何整数，都可以被分解为最多 $3$ 个因数的乘积，且这 $3$ 个因数中，至多只有一个大于 $320$。 存下来，小因数则拿一个 $G_{B, B}$ 的数组预处理。具体见代码。 ### $\color{red}\blacksquare$ CF1635F Closest Pair 这是我第二次写这篇题解，前两次没保存炸掉了（ > 题目大意：两个序列 $x, w$，保证 $x$ 单调递增。每次查询 $\min_{l \le a \lt b \le r} (x_b - x_a) \times (w_a + w_b)$。 首先查询区间的子区间类型问题考虑分治或者扫描线。我试过了，分治好像做不出来，所以我们考虑扫描线。 这个题自变量有两维，所以扫描线 + 李超线段树也做不了。考虑推结论。 令 $L_i$ 与 $R_i$ 为 $i$ 左侧与右侧第一个满足 $w_j \le w_i$ 的位置 $j$。有一个神秘结论是在只考虑全局答案的情况下对于所有 $i$，最终答案一定是 $(L_i, i)$ 或 $(i, R_i)$ 的形式。 Proof: > 假设有一个 $(p, q), p \lt q$ 是最优解且不是上述两种形式之一。 > > 因为其补集情况同理，所以我们钦定 $w_p \le w_q$。 > > 根据定义，我们有 $w_{L_q} \le w_q \rightarrow w_p + w_{L_q} \le w_p + w_q$。且 $L_q \le q \rightarrow x_{L_q} \le x_{q} \rightarrow x_{L_q} - x_p < x_q - x_p$。 > > 显然 $L_q \ne p$，故 $(p, L_q)$ 是一组更优的解，但这与 $(p, q)$ 是最优解矛盾，故原假设不成立。 > > $\square

可以看到证明中的更优解的大小小于假设的最优解的大小，即 q - p + 1 \ge L_q - p + 1，故推广到区间情况的时候这个结论仍然成立。

上树状数组即可。

\color{blue} \blacksquare P4220 [WC2018] 通道

题目大意：给定三棵树，求点对 (u, v) 在三棵树上的距离和的最大值。

对不起，但是我看到这个题花了 \epsilon 秒猜出了这题能用随机化。

距离和的最大值，类似直径，并且这个题拥有与直径同样优秀的性质。思考直径的求法，是双 dfs，第二次 dfs 的起点是上次的最优点，因为以该点为起点的答案不会更劣；

有趣的是，这个题也满足这样的条件，只是两次 dfs 并不能保证找到答案。跑多次即可。

那还说啥，上随机化。然后这个是一个爬山算法，会陷入局部最优解。我们考虑每跑 10 \sim 20 次就重新随机一个点作为起点。最后卡时。

哦对了，19260817 作为随机种子真好用，祝我卡过了。

\color{red}\blacksquare CF1419F Rain of Fire

题目大意：有 n 个平面直角坐标系上的顶点，如果 x_i = x_j 或 y_i = y_j 则 i 可以花费 |x_i - x_j| + |y_i - y_j| 的时间从 i 走到 j，在一个顶点可以停留任意时间。

所有 kt 的时间你必须在任意一个顶点上。求在至多增加一个顶点的情况下能走到所有点的最小 t 值。

首先发现我们可以在顶点 i 等到 (k - 1)t 的时间出发，并只要在 kt 之前到达另一个顶点 j 就满足条件。所以条件就变为若 (i, j) 不超过 t 即可通行。

这东西显然具有单调性，考虑二分 t 的值。问题变成判定性问题。

无向图联通性问题，考虑使用并查集辅助维护。建出来满足题目条件的图。如果连完只剩下一个联通块，那么不用加顶点这个 t 就已经可以满足条件。

接下来我们考虑怎么加一个点。对于每一个点我们都贪心地选择新添加的点，故如果存在一种添加方案，那么添加的点的 x 坐标一定可以表示为 X_i + t、X_i 或 X_i - t，y 同理。

这个时候我们可以把所有 x, y 的决策点都离散化下来 n^2 枚举。然后并查集加边判一下。由于有 n^2 种可能，所以要用可撤销并查集。

可撤销并查集不能路径压缩喵！

时间复杂度 \mathcal{O}(n^2 \log V \log n)，常数不小，大概有个 9 倍。

\color{purple}\blacksquare A5714 「NOIP模拟」御坂网络

题目大意：给一个棵树，每个点有点权，多次询问求包含集合 P 中所有点的联通块的点权与 x 的差的绝对值的最小值。

树上询问点集，一眼虚树，我们先往虚树上面想。

然后绝对值的最小值比较简单，就是求出前驱后继。

问题就变成了询问树链前驱后继。

？直接上主席树 + 树剖就可以了。

### $\color{purple}\blacksquare$ A5712 「NOIP模拟」打洞 > 题目大意：给一个网格图，修改单点加，查询查以 $(x, y), (x + d, y), (x, y + d)$ 三个点围成的三角形的权值和。 确定一个点 $(a, b)$ 被围住的确切条件。$i\le j, x \le a \le x + d, y \le b \le y + d, a + b \le x + y + d$。 这是一个六维偏序，不过可以优化。发现其余三个条件条件可以推出 $ a \le x + d, b \le y + d $ 这两个条件。 也就是说剩下一个四维偏序 $(i, a, b, a + b), (j, x, y, x + y + d)$，用喜欢的方式维护即可。 我用的 cdq 套 cdq 套树状数组，时间复杂度 $\mathcal{O}(n \log^3 n)$，常数较小。具体实现是每一层 cdq 都给左右两段分别染个色再给整段排序。 场上还有手搓 4-D Tree 的大神，时间复杂度 $\mathcal{O}(n ^ {1.75})$，常数还特别大。 ### $\color{red}\blacksquare$ P3266 [JLOI2015] 骗我呢 > 题目大意：求满足 $0 \le a_{i, j} \le m$、$a_{i, j} \lt a_{i, j + 1}$ 且 $a_{i, j} \lt a_{i + 1, j - 1}$ 的二维数组个数。 因为前两个条件，我们一行 $a_i$ 中有且仅有一个位于 $[0, m]$ 的数不在 $a_i$ 中存在，我们考虑依靠这个 dp。 记 $f_{i, j}$ 为第 $i$ 行中只有 $j$ 没有选择的情况。然后你会发现它有转移方程 $f_{i, j} = \sum_{k = 0} ^ {j + 1} f_{i - 1,k} = f_{i, j - 1} + f_{i - 1, j + 1}$。 然后可以考虑图像意义，斜线不好考虑，你考虑拉伸一下坐标轴。 变成从 $(0, 0)$ 到 $(n + m + 1, n)$ 且不经过 $y = x + 1$、$y = x - m - 2$ 直线的方案数。 这个直接反射容斥好了。 ## 后续的题目没有 jzp 的评级，所以不写了 ### CF2215E / P16537 [THUPC 2026 决赛] 星图重绘 不会做 [省选联考 2026] 星图 / starmap，所以来做这个题。 考虑和谐三角形的双射，即三点坐标在按照 $x$ 坐标从大到小排序之后 $y$ 坐标不单调，这是比较显然的。 那么我们考虑按 $x$ 坐标从大到小的顺序依次加入节点。由于要求三角形之间不相交，所以我们与新加入的点组成合法三角形的店只会**暴露在左侧**。具体的，如下图标红的点。 ![](https://cdn.luogu.com.cn/upload/image_hosting/g50qs86q.png) 我们称这些点为左侧点。不难发现这些左侧点在按照 $y$ 轴从小到大排序后 $x$ 坐标是单谷的，因为如果不是则两个谷至少会组成一个合法三角形。 考虑哪些左侧点会与新加入的点形成合法三角形。显然，在最优情况下，每个三角形组成所需的左侧点是相邻的。再通过一些简单的手玩可以发现合法的左侧点对是 *$y$ 坐标恰好包住新加入点* 的左侧点对和 *其中一端是波谷* 的左侧点对。 ![](https://cdn.luogu.com.cn/upload/image_hosting/jn9ig79q.png) 这个信息可以轻松通过 set 维护。由于每个点至多被加入并删除一次，所以均摊下来时间复杂度 $\mathcal{O}(n \log n)$。 ### P12358 [eJOI 2024] 奶酪交易 / Cheese 掉橙就掉橙吧，bro 不想亮勾也不想写题解了。 考虑具象化条件 $i, j, A, B$，即 $P_{j} = P_{i} + A + Bk$，$k$ 为整数，并非自然数。这个形式比较抽象，考虑转化成同余的形式（不是这个我想到了啊为什么做不出来啊喂）。 $$ P_j - P_i \equiv A \pmod B. $$ 这个同余关系可以通过带权边表示，又因为 $B \le 2^{15}$，我们考虑直接开 $15$ 个带权并查集用于维护这样的关系。剩下的地方就是带权并查集的基础内容了。 本题略微卡常，需要发挥技能。 ### P16357 [BalticOI 2026] Blocks > 。造构的恶可可恶的构造。 不难将原题面条件抽象成所有同颜色位置距离中间点的距离之和为 $0$。观察到 $n$ 的奇偶会影响答案，我们分开讨论。 如果 $n$ 为偶数，那么一定不会出现出现次数为奇数的颜色，因为 $\frac{n + 1}{2}$ 不是整数且分母包含 $2$，而 $\frac{A}{2k + 1}$ 的分母不可能包含 $2$。剩余情况即 $n$ 与所有颜色出现次数均为偶数的情况，此时的构造是简单的，在中间线两头一一对称构造即可（回文，~~呼应文章的开头~~）。 考虑 $n$ 为奇数的情况。我们可以将其重新编号 $-\frac{n - 1}{2}, \cdots, -2, -1, 0, 1, 2, \cdots ,\frac{n - 1}{2}$，此时要求即转化为 $\sum _ {i \in C} i = 0$。 观察到 $i = 0$ 的位置最优的方案是填入一个只出现一次的数，且这样的数不能出现大于一个。如果没有这样的数，可以将一个奇数次拆成 $1$ 和一个偶数次再填入。同理剩余的奇数可以拆成 $3$ 和一个偶数。 那么我们现在剩余若干个出现次数为 $3$ 的数，记其个数为 $X$。我们尝试一种最优的构造将 $1, \cdots, X$ 填入 $[-1.5X, 1.5X]$ 中。 ![](https://cdn.luogu.com.cn/upload/image_hosting/gj7dj9d6.png) 第一次我们将其按照如图方式放置，即： $$ (-i) + \left(-\frac{X}{2} - i\right) + \left( \frac{X}{2} + 2i \right) = 0. $$ ![](https://cdn.luogu.com.cn/upload/image_hosting/nk0hct0n.png) 第二次即： $$ (-X-i) + \left(\frac{X}{2} - i + 1\right) + \left( \frac{X}{2} + 2i - 1 \right) = 0. $$ （两次都有 $i \in \left[1, \frac{X}{2}\right]$）。 我们就做完了！代码自己写。 :::