分类

$\color{Gray}{writing}$：还在写代码。

$\color{Green}{Easy}$：一眼题。

$\color{Blue}{Median}$：经过思考可以做出来。

$\color{Yellow}{Hard}$：看完题解立马理解。

$\color{Orange}{Insane}$：看完题解经过一段时间的思考能够理解。

$\color{Red}{Supreme}$：看完题解经过长久思考才理解。

CF1982F Sorting Problem Again $\color{Blue}{Median}$

转换还是比较显然的，就是感觉特判有点多。

P4198 楼房重建 $\color{Green}{Easy}$

模版，一眼。

CF1340F Nastya and CBS $\color{Red}{Supreme}$

第一次切 *3300。

由于 $n = 10^5$ 我们考虑分块，对块内进行暴力重构。

如果一个块本身不是形如 一堆右括号 + 一堆左括号 的话，显然是不合法的。

然后我们考虑用哈希来模拟匹配就可以了。

码量有点恐怖（使用了 AI 帮忙 debug）。

AT_abc244_h Linear Maximization $\color{Blue}{Median}$

将 $A x + B y$ 转换为 $B (x \frac{A}{B} + y)$ 即可。

注意特判 $B = 0$，修了好久。

P3515 [POI 2011] Lightning Conductor $\color{Yellow}{Hard}$

被诈骗了，原本是线段树的作业，结果是用决策单调性做。

还是分治好写。

CF407E k-d-sequence $\color{Orange}{Insane}$

简单题，不知道为什么是 *3100 漏盘了一件事，我错了。

考虑枚举右端点 $r$，则一段区间 $[l, r]$ 合法当且仅当：

• $[l, r]$ 中没有相同的数

• $[l, r]$ 的差分数组的 gcd 为 $d$ 的倍数。

• $ \frac{max_{l \leq i \leq r} a_i - min_{l \leq i \leq r} a_i}{d} \leq r - l + 1 + k $。

可以用两种线段树（一个维护 $a$，一个维护 $a$ 的差分数组）实现，时间复杂度 $O(n (\log n + \log V))$。

至于如何算第三个条件，转换为 $(max - min + l) \leq (r + k + 1) \times d$，是不是瞬间简单了，可以线段树二分。

记得特判 $d = 0$。

P13788 「CZOI-R6」Permutation and Subsequence $\color{Green}{Easy}$

还是一眼题。

P13789 「CZOI-R6」游戏 $\color{Green}{Easy}$

把绝对值拆开即可，修了好久。

P13790 「CZOI-R6」Border $\color{Blue}{Median}$

考虑枚举长度+哈希即可。

CF773E Blog Post Rating $\color{Red}{Supreme}$

好题，让我大脑消失。

首先肯定会让 $a_i$ 单调不降，然后我们会发现一个转折点 $p$，在 $a_i < p$ 时都是 $F \leftarrow F - 1$，然后 $F$ 才单调不降。

考虑求出这个转折点 $p$，令 $c_i$ 表示小于等于 $i$ 的数的数量，容易发现 $p$ 为第一个满足 $- c_i \leq i$ 的数，这等价于 $0 \leq i + c_i$，使用线段树二分即可。

搞出这个转折点后，我们会发现 $p$ 之后的 $a_i$ 对答案的贡献为“最终答案不会超过 $a_i + (n - i)$，很容易拆成 $n$ 和 $a_i - i$，变为维护 $i - c_i$。

时间复杂度 $O(n \log n)$。

（代码基本上抄 Alex_Wei 的）。

P4425 [HNOI/AHOI2018] 转盘 $\color{Orange}{Insane}$

（这居然是单侧递归线段树？？？我的一辈子）。

考虑转换为以下问题：

你从 $t$ 时刻开始出发，每次可以往后移动一步或者停留。每个点在 $T_i$ 消失，求最小的 $t$，使得你能走遍所有点。

显然停留一定不优，所以你会一直走（最重要的观察）。

然后我们破环为链，枚举起点 $i \in [n, 2n)$，则可以得出：

$$t = \min_{i - n \leq j \leq i} (T_j - j) + i$$

令 $a_i = T_i - i$，则：

$$\begin{aligned} & ans = \min_{n \leq i < 2n} (\max_{i - n \leq j \leq i} a_j + i) \\ \iff & ans = \min_{1 \leq i \leq n} (\max_{i \leq j \leq i + n - 1} a_j + i) + n - 1 \end{aligned} $$

由于 $a_i > a_{i + n}$，所以可以推出：

$$ans = \min_{1 \leq i \leq n} (\max_{i \leq j \leq 2n} a_j + i) + n - 1 $$

所以我们只关心后缀最大值。

单侧递归线段树，启动！

P3081 [USACO13MAR] Hill Walk G $\color{Green}{Easy}$

omg so ez 简直是李超线段树板子题。

CF39I Tram $\color{Yellow}{Hard}$

看错题了，ctmd。