Problems（2026/01 ~ 2026/03）

back。

$\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}$

$\log W \le 63$，考虑枚举 popcount 的值 $p$ 再算贡献。

扫描线枚举 $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，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$ 作为随机种子真好用，祝我卡过了。