【做题记录】洛谷省选计划 2021 Week 1 做题记录

前言

本文为洛谷省选计划 2021 Week 1 的做题记录。

每道题的超链接后面都有该题的通过状态，其中 AC 表示已经通过，NC 表示未完成。

正文

P7706 「Wdsr-2.7」文文的摄影布置 AC

题解：

考虑线段树，那么问题的关键在于如何合并左右两侧的信息。

我们发现三元组 $(i, j, k)$ 是有顺序 $i < j < k$ 的，所以我们可以简单分讨三个位置在左右两侧的分布情况，然后对涉及到的变量进行维护即可。

这样维护看似存在一些问题，但是解的最优性可以保证合法性。

代码实现

P6617 查找 Search AC

题解：

注意到 $w$ 是固定的，那么每个数 $u$ 仅会和一个数 $v = w - u$ 配对。

一个做法是用 $\texttt{set}$ 维护每个位置 $i$ 的后继 $nxt_i$ 。但是，由于这题的特殊性，直接维护会导致单点修改时有很多位置 $i$ 的后继 $nxt_i$ 发生变化。

我们不妨改变一下 $nxt_i$ 的定义：当且仅当位置 $i$ 的后面不存在位置 $j$ 满足二者的后继相同时， $nxt_i$ 等于其精确值，否则我们认为其等于 $n + 1$ 。

这样显然不会影响最优性，并且每次单点修改时，发生变化的 $nxt_i$ 减少至了常数个，是非常好的优化。

注意实现时的细节有点小多。

代码实现

P5069 [Ynoi2015] 纵使日薄西山 AC

题解：

首先，如果位置 $i$ 被选中，那么位置 $i - 1$ 和 $i + 1$ 必然不会被选中。所以，被选中的位置必然不存在相邻关系。

这样的话，我们可以考虑用线段树维护。对于每一个子段 $[l, r]$ 而言，我们需要维护 $[l + 1, r - 1], [l + 1, r], [l, r - 1], [l, r]$ 四个子段的答案，以避免选中相邻两个位置的情况出现。同时，我们还需要维护对于上述四种情况中的每一种情况而言， $l$ 和 $r$ 是否会被选中，这样上述四种情况的答案就可以维护了。

实际上，这个做法可以支持更强的修改。

代码实现

P3747 [六省联考 2017] 相逢是问候 AC

题解：

考虑到每个位置的值形如一个幂塔 $c^{c^{c^{\cdots}}}$ ，根据扩展欧拉定理，幂塔的最底层需要对 $p$ 取模，次底层需要对 $\varphi(p)$ 取模，次次底层需要对 $\varphi(\varphi(p))$ 取模，以此类推。

注意到 $\varphi(p)$ 在层层嵌套的情况下是会不断减小直至其值等于 $1$ 的。那么，当 $\varphi(p)$ 不断减小，直至最高层的指数固定为 $[c > 0]$ 时，该位置的值就不变了。

此时嵌套的层数是 $\mathcal{O}(\log_2 p)$ 级别的（对于偶数，嵌套一次后规模至少会缩小一半；对于奇数，嵌套一次后一定会变成偶数），这提示我们两件事情：

我们用势能线段树，对每个位置暴力操作，这样总操作次数是 $\mathcal{O}(n \log_2 p)$ 的；
计算幂次如果用快速幂会多带一个 $\log$ ，我们不妨预处理出所有模数，然后用光速幂预处理。

注意两点：

根据扩展欧拉定理，求幂次时我们需要注意判断指数是否大于等于当前的模数。
当 $\varphi(p)$ 第一次减小至 $1$ 时，幂塔最高层的指数为 $[a_i > 0]$ ，如果 $a_i = 0$ ，那么再次对该位置操作可能会使该位置的值改变。所以，预处理的模数中要包含两个 $1$ ，这样最高层指数才能固定为 $[c > 0]$ ，无论层数如何增大，这个位置的值也不会变。

代码实现

P4344 [SHOI2015] 脑洞治疗仪 AC

题解：

$0$ 操作和 $2$ 操作都可以用线段树平凡地维护，那么关键在于如何维护 $1$ 操作。

其实也很简单，我们用类似线段树二分的思想，依次考虑当前剩下的 $1$ 是否能够完全覆盖左右两侧的子段即可。

代码实现

CF280D k-Maximum Subsequence Sum AC

题解：

注意到我们可以对这道题进行费用流的建模。由于比较显然，这里就不多赘述了。

直接对其跑最大费用最大流显然是不行的，我们需要想办法优化。

由于这个费用流的模型极其简洁，因此我们很难对点数和边数进行一个有效的优化，那么我们不妨考虑模拟费用流。

费用流是具有凸性的，也即如果我们依次找出若干条增广路并对其施加 $1$ 的流量，那么我们得到的费用必然是单调不增的。

有了这个性质，我们可以考虑模拟找增广路的过程，如果某一次得到的费用为非正数就停止找增广路。可以发现这其实就是将区间内的最大子段和找出来，然后将对应的子段取反，用线段树维护即可。

由于 $k$ 很小，所以我们模拟找增广路的过程的复杂度是可以接受的。

代码实现

P4062 [Code+#1] Yazid 的新生舞会 AC

题解：

发现权值是 $\mathcal{O}(n)$ 级别的，那么我们可以考虑枚举权值并计算每一个权值的贡献。

对于当前枚举到的权值 $w$ ，我们设 $S_i$ 为 $1 \sim i$ 中权值等于 $w$ 的位置数量，那么区间 $[l + 1, r]$ 是合法的区间的充要条件为 $(S_r - S_l) > (r - l) - (S_r - S_l)$ ，移项可得 $S_r \cdot 2 - r > S_l \cdot 2 - l$ 。

设 $P_i = S_i \cdot 2 - i$ ，现在问题转化为：对于每一个 $r$ ，统计 $[0, r - 1]$ 中有多少 $l$ 满足 $P_r > P_l$ 。

直接做必然是 $\mathcal{O}(n^2)$ 的。

我们不妨找找 $P_i$ 的规律，可以发现它是呈若干段公差为 $-1$ 的等差数列的形式的，并且总段数是 $\mathcal{O}(n)$ 级别的，那么我们可以考虑在每一段上下功夫。

考虑设 $c_j$ 表示 $P_i = j$ 的 $i$ 的个数，那么对于 $P_i = x$ 的位置 $i$ 而言，它的答案即为 $\displaystyle \sum_{j = -n}^{x - 1} c_j$ ，也即 $c_j$ 的一段前缀和。我们不妨设其为 $T_{x - 1}$ 。

而对于一个段而言，段内是不会互相贡献的（因为 $P_i$ 递减），设段中 $P_i$ 所覆盖到的值域为 $x \sim y$ ，那么其答案即为 $\displaystyle \sum_{i = x - 1}^{y - 1} T_i$ ，也即 $T_i$ 的一段区间和。

注意到一个段对 $c_j$ 的贡献相当于区间加 $1$ ，那么问题就变为了区间加、区间查询二阶前缀和问题。

其实我们可以直接维护 $T_i$ ，这样原来的区间加就变为了区间加等差数列，这个是可以用线段树的标记维护的。

代码实现

CF1446D2 Frequency Problem (Hard Version) AC

题解：

首先特判掉 $n = 1$ 和全局众数有多个的情况，那么接下来的所有情况中全局众数仅有一个，不妨设其为 $u$ 。

这个题的 $\operatorname{key}\operatorname{observation}$ 是：答案的子段必然包含全局众数 $u$ 。如果不是，说明子段中存在一个数 $v$ ，出现次数大于 $u$ ，那么我们向外扩展子段的左右端点，直到某一时刻 $u$ 和 $v$ 的出现次数相同为止，这样我们就得到了一个更优解。显然这样的时刻必然是存在的。

那么 $\text{D1}$ 的做法就是：枚举每个非 $u$ 的数 $w$ ，令 $u$ 表示 $1$ ， $w$ 表示 $-1$ ，其它数表示 $0$ ，求最长的权值和为 $0$ 的子段。这个是平凡的。

对于 $\text{D2}$ ，我们可以考虑根号分治，那么出现次数大于 $\sqrt{n}$ 的数就可以套用 $\text{D1}$ 的做法。

出现次数小于等于 $\sqrt{n}$ 的数怎么做？我们不妨枚举这个出现次数 $t$ ，然后用双指针维护 “最长的满足所有数的出现次数都不超过 $t$ 的子段” 即可。

代码实现

CF765F Souvenirs AC

题解：

考虑把询问离线下来，按照右端点从小到大的顺序处理。

设当前处理的右端点为 $r$ ，记 $ans_i$ 表示所有左端点为 $i$ 且右端点在 $[i, r]$ 内的子段的答案，那么询问时直接查询后缀最小值即可。

注意对于一对可能会对答案造成贡献的二元组 $(i, j)$ （满足 $i < j$ ），只会存在 $a_i \ge a_j$ 和 $a_i \le a_j$ 两种情况，并且由于两种情况是相互对称的，因此下文默认仅考虑第一种情况。

现在我们来考虑这样一个做法：对于当前处理到的右端点 $r$ ，首先找到 $i$ 左侧的最右侧的一个位置 $x$ ，满足 $a_x \ge a_i$ ，并更新 $ans_x$ 的值，然后我们再找到 $x$ 左侧的最右侧的一个位置 $y$ ，满足 $a_y \ge a_i$ 且 $a_y < a_x$ ，并更新 $ans_y$ 的值，以此类推直到我们无法找到合法的位置为止。

这个做法的复杂度显然是错误的，但我们可以尝试在不影响答案的前提下删去部分贡献，以此降低算法的复杂度。

假设我们现在找到了 $i$ 左侧的最右侧的一个位置 $x$ ，满足 $a_x \ge a_i$ ，那么对于我们接下来要找的一个位置 $y$ ，如果有 $a_y - a_i \ge a_x - a_y$ ，那么我们完全没有必要更新 $y$ 这个位置的值，也即 $y$ 这个位置需要满足 $a_y \ge a_i$ 且 $a_y \cdot 2 < a_i + a_x$ 。

这样的话，设 $w$ 为值域，那么我们显然最多只会找到 $\mathcal{O}(\log_2 w)$ 个这样的位置，复杂度就大大地降低了。

对于找到合法的位置的部分，我们用主席树维护即可；对于 $ans_i$ ，我们用树状树组维护即可。

最后，本题实际上还存在一个支持强制在线的分块做法，感兴趣的读者可以参考题解区。

代码实现

P2042 [NOI2005] 维护数列 AC

题解：

六个操作都是平衡树的经典操作，因此直接维护即可。本题最大的难点在于实现。

代码实现

P5482 [JLOI2011] 不等式组 AC

题解：

特判掉 $a = 0$ 的直线，那么对于每一条 $a \ne 0$ 的直线而言，满足条件的 $x$ 一定是连续的。

而我们又可以注意到 $k$ 的值域较小，所以我们直接在 $k$ 的值域上用线段树维护即可。

代码实现

P4036 [JSOI2008] 火星人 AC

题解：

考虑 $\mathcal{LCP}$ 的经典求法：二分 + 哈希。

所以，我们直接二分答案，然后用 $\mathcal{FHQ-Treap}$ 分裂出对应的两个部分，再判断哈希值是否相等即可。

其它两个操作都是平凡的，不再赘述。

代码实现

P3215 [HNOI2011] 括号修复 / [JSOI2011] 括号序列 AC

题解：

前三个操作都可以通过在 $\mathcal{FHQ-Treap}$ 上打标记维护，难点在于询问操作。

结论是：设左括号的权值为 $-1$ ，右括号的权值为 $1$ ，最大前缀和为 $a$ ，最小后缀和为 $b$ ，那么答案即为 $\displaystyle \lceil \frac{a}{2} \rceil + \lceil \frac{-b}{2} \rceil$ 。

证明：首先，最靠前的最大前缀和最靠后的最小后缀是没有交集的。如果有，不妨设其为 $[l, r]$ ，那么 $[l, r]$ 内右括号的个数既大于又小于左括号的个数，这显然是矛盾的。

那么，我们设最靠前的最大前缀和最靠后的最小后缀分别为 $x$ 和 $y$ ，则 $x < y$ 且若区间 $(x, y)$ 存在就必然是一个合法的括号序列。

这样，我们就只需要修改 $x$ 和 $y$ 的部分了。修改它们的代价都是显而易见的。

注意标记下传的顺序：区间的取反标记下传必须在覆盖标记下传的前面，因为取反标记会把覆盖标记也取反。

代码实现

P6105 [Ynoi2010] y-fast trie AC

题解：

我们可以把所有元素都 $\bmod~\text{C}$ ，这样只有两种数对能够对答案造成贡献：

满足 $x + y \ge \text{C}$ 的数对 $(x, y)$ ，此时它们的贡献为 $x + y - \text{C}$ ；
满足 $x + y < \text{C}$ 的数对 $(x, y)$ ，此时它们的贡献为 $x + y$ 。

对于第一种数对，我们直接找出最大值和次大值即可，那么主要的问题在于如何维护第二种数对。

注意到对于数 $x$ 而言，集合中最优的能够与其配对的数 $y$ 是唯一的，但如果我们直接如此维护，每次修改的复杂度其实是很高的。

类似 P6617，我们可以考虑通过贪心的思想，减少需要维护的数对。具体地，对于两个数对 $(x, y)$ 和 $(y, z)$ ，如果有 $x > z$ ，那么我们就不维护 $(y, z)$ 这个数对，也即我们维护的所有数对 $(x, y)$ 都满足两个数都是集合中最优的能够与对方配对的数。

这样，修改的复杂度就大幅度地降低了。我们如果用 $\texttt{multiset}$ 维护集合 $S$ 以及数对的集合，那么复杂度为 $\mathcal{O}(n \log_2 n)$ 。

为什么集合 $S$ 也要用 $\texttt{multiset}$ 维护呢？因为题目中并没有保证所有 $x \bmod \text{C}$ 不重复哦。

（这题还存在一种更加易于实现的方法是用线段树维护 —— 由于第二种数对满足 $x < \text{C} - y$ ，因此我们对值域建线段树， $\texttt{Pushup}$ 时考虑左半区间最优的 $x$ 和右半区间最优的 $\text{C} - y$ 即可，不过这个方法在这题被卡空间了。）

代码实现

P5610 [Ynoi2013] 大学 AC

题解：

发现每个数 $a_i$ 最多会被除 $\mathcal{O}(\log_2 a_i)$ 次，所以问题的关键在于如何找到需要被除的位置。

考虑每个数 $a_i$ 的因数个数为 $\mathcal{O}(\sqrt[3]{a_i})$ ，我们不妨对每个因数维护一个数组，每次在数组上二分出一个范围，然后对这个范围内的数进行操作，这样问题的关键又转化为如何快速地动态删除一个位置。

对于这个问题，我们可以考虑用并查集维护，若某个点需要被删，那么我们就可以将其和下一个位置合并，这样配合路径压缩，单次删除的复杂度就为 $\mathcal{O}(\alpha(n)) \approx \mathcal{O}(1)$ 。

最后，本题十分卡常，我们不能用 $\texttt{vector}$ 存信息。每个数的因数可以考虑用邻接表存储，而和并查集有关的数组可以手写内存池，这样常数会减小很多。

代码实现

P5068 [Ynoi2015] 我回来了 AC

题解：

我们发现，对于一次伤害值为 $d$ 的亵渎，它能够在初次释放之后再次释放 $i$ 次，当且仅当对于所有的 $j \in [1, i]$ ，都存在随从满足血量在区间 $[d \cdot (i - 1) + 1, d \cdot i]$ 内。我们不妨用二元组 $(d, i)$ 表示这样的一个区间。

注意到这样的区间个数是 $\mathcal{O}(n \ln n)$ 的，那么，我们可以考虑复杂度和区间个数有关的做法。

由于我们只会不断地加入随从，因此这些区间内随从的存在性是具有单调性的。

把所有操作离线下来，设 $a_i$ 表示血量为 $i$ 的随从最早在哪个时刻出现， $b_{d, i}$ 表示 $(d, i)$ 所代表的区间最早在哪个时刻会存在随从， $c_{d, i}$ 表示伤害为 $d$ 的亵渎最早在哪个时刻能够在初次释放之后再次释放 $i$ 次。

$a_i$ 可以简单维护， $b_{d, i}$ 可以用 $\operatorname{ST}$ 表维护， $c_{d, i}$ 也可以通过简单的转移式得到。

求出上面三个数组后，我们考虑如何处理询问。

注意到 $(d, i)$ 所代表的区间会对 $c_{d, i}$ 之后且包含 $d$ 的询问造成 $1$ 的贡献，这样的话做法就呼之欲出了：我们按照时间顺序处理每一组询问，然后用树状数组维护即可。

代码实现

CF453E Little Pony and Lord Tirek AC

题解：

假设当前操作的时刻为 $t$ ，那么对于一个上一次操作的时刻均为 $t'$ 的区间，它们的贡献可以用主席树维护。

具体地，对于第 $i$ 个位置，它的操作次数上界是 $\lfloor\dfrac{m_i}{r_i}\rfloor$ ，那么我们可以统计所有上界不小于 $t - t'$ 的位置，它们的贡献等于所有 $r_i$ 的和乘上 $t - t'$ ，而其它位置的贡献即为 $m_i$ 的和。注意这里要对 $r_i = 0$ 的位置特判。

如何维护这样的区间呢？我们发现存在区间推平的操作，那么我们完全可以考虑颜色段均摊，直接用 $\texttt{set}$ 维护即可。

注意初始时每个位置的 $s_i$ 并不一定为 $0$ ，那么我们需要在每个位置第一次被覆盖时暴力计算一遍该位置的答案。这样由于每个位置最多被计算 $\mathcal{O}(1)$ 次，因此时间复杂度是正确的。

代码实现

CF1340F Nastya and CBS AC

题解：

如何判断一段括号序列是否合法？显然暴力的做法就是用栈维护。

现在，我们需要考虑的是：如何用数据结构模拟栈维护的过程。无论是下文将要提到的线段树还是分块，它们的本质都是把询问的子段通过某种方式进行分组，然后将若干组信息合并。

那么，最主要的问题是如何合并信息。不妨设我们现在有左右两组信息，我们需要将它们合并为一组。

注意到如果两组中的一组存在错配的情况，那么合并后的括号序列必然是不是合法的。对于一个不存在错配情况的括号序列，如果我们消除掉中间合法的部分，那么剩下的部分一定是一段右括号加一段左括号。这样的话，我们仅需维护前后两段的哈希值即可合并，同时也可以判断合并后的括号序列是否存在错配的情况。

官方的题解是采用线段树套可持久化平衡树，这样时间复杂度为 $\mathcal{O}(n \log_2^2 n)$ ，空间复杂度为 $\mathcal{O}(n \log_2 n)$ 。基于该做法，兔队给出了一个线段树的做法，时间复杂度不变，而空间复杂度降至了 $\mathcal{O}(n)$ 。实际上，本题一个比较大众的做法是用分块维护上述信息，这样时间复杂度为 $\mathcal{O}(n \sqrt{n})$ ，空间复杂度为 $\mathcal{O}(n)$ 。