Problems（2025 年及更早）

back。

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$，只能考虑优化状态。

$l$ 和 $r$ 不能舍弃，只能将 $x$ 改成 $0/1$ 代表胜出的是左端点或右端点。

我们发现原来的 $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$。

如图，红蓝两个分别是空闲可以填入的格子；事实上，红蓝两个地方可以分开构造，两者相互独立。

考虑对于每一个可以填入的格子 $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

跟出题人对上脑电波了。

题目大意：一个 $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$ 相等，所以这样的区间就算计入答案也不会影响最终答案。