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

前言

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

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

正文

可持久化与树套树

P3567 [POI2014] KUR-Couriers AC

题解：

答案最多仅会有一个，因此用可持久化线段树 + 线段树二分做即可。

当然也可以用摩尔投票法做，不过注意对于查询出的答案 $x$ ，我们还需验证其是否合法，这个可以对每个值开一个 $\texttt{vector}$ ，然后在其上二分。

代码实现

P2839 [国家集训队] middle AC

题解：

考虑二分答案 $x$ ，把大于等于 $x$ 的数赋权为 $1$ ，小于 $x$ 的数赋权为 $-1$ ，那么我们仅需查询是否存在合法的区间满足区间和大于等于 $0$ 即可。

这个我们以值域为轴建主席树，然后求 $[a, b]$ 的最大后缀和、 $[c,d]$ 的最大前缀和以及 $(b, c)$ 的和即可。

代码实现

P3402 可持久化并查集 AC

题解：

状态压缩的并查集由于复杂度是均摊的，因此不能够可持久化。我们考虑按秩合并。

用可持久化线段树维护 $fa$ 数组和 $si$ （或 $dep$ ）数组，然后模拟操作即可。

代码实现

P3293 [SCOI2016] 美味 AC

题解：

考虑按位贪心，那么每一位上的问题相当于对于一个值域区间询问其中是否存在值，这个用主席树维护即可。

代码实现

P4899 [IOI2018] werewolf 狼人 AC

题解：

先考虑作为人形时的行程，我们令每条边的权值为其两端点编号的较小值，并对其建立最大生成树的 $\mathcal{Kruskal}$ 重构树，那么这个点能够走到的节点即为该树上的一颗子树，而子树可以用区间来表示。

那么我们再令每条边的权值为其两端点编号的较大值，并对其建立最小生成树的 $\mathcal{Kruskal}$ 重构树，问题就变为了求出 $s$ 和 $t$ 分别能够到达的子树，以及询问二者是否有交集，前者用树上倍增维护即可，后者相当于静态二维数点，用主席树维护即可。

代码实现

P3302 [SDOI2013] 森林 AC

题解：

先考虑不带第二种操作怎么做：我们倍增找出两个点的 $\mathcal{LCA}$ ，然后用可持久化线段树 + 树上差分做即可。

发现对于一棵树而言，我们仅需维护好它的倍增表和可持久化线段树即可求解，但这两者都不支持快速合并，怎么办呢？启发式合并即可。

代码实现

P4396 [AHOI2013] 作业 AC

题解：

稍加转化就能变为经典的三维数点问题， $\mathcal{CDQ}$ 分治或莫队 + 值域分块均可。

代码实现

P4054 [JSOI2009] 计数问题 AC

题解：

二维树状数组的模板题。

怎么实现？实际上就是在两个维度做和一维树状数组一模一样的循环即可。

代码实现

P3759 [TJOI2017] 不勤劳的图书管理员 AC

题解：

考虑答案的表达式： $\displaystyle \sum_{i = 1}^{n - 1} \sum_{j = i +1}^n [a_i > a_j] \cdot (v_i + v_j)$ 。发现修改到的位置个数是 $\mathcal{O}(1)$ 的，那么我们不妨考虑每个位置对这个表达式的贡献。

这样，问题就转化为了在线的带权二维数点问题，用树套树做即可。注意由于空间限制比较紧，所以要回收节点。

代码实现

P3157 [CQOI2011] 动态逆序对 AC

题解：

考虑引入时间一维，这样每一个元素相当于一个由被删除的时间 $t_i$ （若该元素未被删除则认为其为 $m + 1$ ）、所在的位置 $p_i$ 、所具有的数值 $v_i$ 所组成的三元组。

分析可知，对于一个元素 $(t_i, p_i, v_i)$ ，它能够被元素 $(t_j, p_j, v_j)$ 贡献，当且仅当 $t_i < t_j$ ，且 $p_i < p_j, v_i > v_j$ 或 $p_i > p_j, v_i < v_j$ 中的其一满足。

这样，原问题就转化为了经典的三维偏序问题，我们用树套树或 $\mathcal{CDQ}$ 分治解决均可。注意到时间维的限制是单一的，因此我们对时间维进行分治会比较方便。

代码实现

P3332 [ZJOI2013] K 大数查询 AC

题解：

考虑用树套树来维护信息。由于值域上是单点修改而位置上是区间修改，因此外层线段树用于维护值域，内层线段树用于维护位置。

修改操作直接做即可，查询操作在外层的线段树上二分， $\mathcal{O}(\log_2n)$ 地判断二分区间的收缩方向即可。

代码实现

P5445 [APIO2019] 路灯 AC

题解：

我们考虑用 $\texttt{set}$ 维护极长的全 $0$ 段，那么对于一个为 $0$ 的位置 $l$ ，设其后继为 $r$ ，则 $a$ 能够到达 $b$ 当且仅当存在一组 $(l, r)$ 满足 $l < a$ 且 $r \ge b$ ，问题转化为了一个二维偏序问题。

那时间维的限制怎么维护呢？直接扫描所有极长全 $0$ 段的时间复杂度不对，我们不妨考虑在修改到的 $\mathcal{O}(1)$ 个极长全 $0$ 段上做文章。

我们不妨假设从当前时刻起，其之后所有时刻都不存在修改，这样就很好维护了：设当前时刻为 $t$ ，那么对于加入的一个极长全 $0$ 段，我们对其修改到的矩形加上 $q - t +1$ ，删除同理。

代码实现

P4592 [TJOI2018] 异或 AC

题解：

如果我们有办法得到所有节点的权值的 $\mathcal{Trie}$ 树，那就是经典问题了 —— 在其上二分即可。

对于树上的子树和链的查询问题，树套树无论是时间还是空间都不是很优，我们用可持久化 $\mathcal{Trie}$ 做即可。

代码实现

P5795 [THUSC2015] 异或运算 AC

题解：

注意到 $p, n$ 都很小，因此对于每个询问我们可以先暴力枚举行，然后维护列上的数据结构。

列上的数据结构需要支持 $\mathcal{Trie}$ 树上的二分，用可持久化 $\mathcal{Trie}$ 即可。

代码实现

CF702F T-Shirts AC

题解：

考虑一种暴力做法：将物品排序，然后按照顺序考虑每一件物品，再扫描每一个人是否能够购买。

我们用平衡树维护购买，那么我们需要将能够购买的人的剩余钱数减去对应的价格。

直接做显然会超时，而分裂为 $[0, c)$ 和 $[c, +\infty)$ 两个部分并对后面一个部分打减标记又会使得左右两个部分有重，这样就会无法合并。

我们不妨将后面这一部分再分裂为 $[c, c\cdot 2)$ 和 $[c\cdot 2, +\infty)$ 两个部分，对于前面的部分，我们暴力减之后暴力插入，对于后面的部分，我们可以直接打减标记。

注意到对于前面的部分，每个人每次的剩余钱数会缩小至原来的至多 $\dfrac{1}{2}$ ，因此复杂度是正确的。

代码实现

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)$ 。

代码实现

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$ ，我们用树状树组维护即可。

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

代码实现

P2824 [HEOI2016/TJOI2016] 排序 AC

题解：

直接排序并不好做，但是我们是否能够二分答案 $x$ 并判断答案是否大于等于 $x$ 呢？是可以的。

我们把大于等于 $x$ 的部分赋权为 $1$ ，小于 $x$ 的部分赋权为 $0$ ，那么排序就可以用区间查询 + 区间覆盖来模拟了，用线段树做即可。

代码实现

根号算法

P3245 [HNOI2016] 大数 AC

题解：

我们设区间 $[i, n]$ 组成的数为 $q_i$ ，那么一个区间 $[l, r]$ 合法的充要条件为 $\displaystyle \frac{q_l - q_{r +1}}{10^{r - l +1}} \equiv 0 \pmod p$ 。

若 $p \mid 10$ ，那么一个区间是否合法仅和右端点有关，这个随便维护即可。

否则，原式可以改写为 $q_l \equiv q_{r+1} \pmod{p}$ ，这个就和这题一样了，用莫队做即可。

代码实现

P3604 美好的每一天 AC

题解：

一个区间合法当且仅当至多一个字符出现次数为奇数，而奇偶性让我们想到异或。

我们不妨设前缀状态为 $p_i$ ，那么一个区间的状态即为 $p_{l - 1}~\texttt{xor}~p_r$ 。

考虑莫队，加入一个位置时，我们考虑有多少个位置和这个位置的 $p_i$ 异或得到的状态是合法的，这个由于字符集大小为 $26$ ，因此我们维护一个大小为 $2^{26}$ 的数组即可。删除同理。

代码实现

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$ 的子段” 即可。

代码实现

CF896E Welcome home, Chtholly AC

题解：

首先对序列分块，那么每个块的最大值是不增的。

值域很小，那么我们如果对于每个块都能够 $\mathcal{O}(1)$ 地将最小值减小 $1$ ，时间复杂度是可以接受的。

所以我们可以对每个块在值域上维护并查集，同时维护整块最大值 $mx$ 。

修改时，散块直接重构，整块考虑如下做法：如果 $mx$ 不超过 $x \cdot 2$ ，我们就枚举 $[x + 1, mx]$ 这一段，与 $[1, mx - x]$ 合并，同时更新 $mx$ ；否则我们枚举 $[1, x]$ 这一段，与 $[x + 1, x \cdot 2]$ 合并，然后打上全局减标记。

查询时枚举整块和散块直接查询即可。

代码实现

CF1588F Jumping Through the Array AC

题解：

修改操作是单点修改，那么我们可以考虑操作分块。

每个块中 $2$ 和 $3$ 操作最多会涉及到 $\mathcal{O}(\sqrt{n})$ 个点，那么我们可以把一些链缩为一点。

具体的，我们以一个被修改点的后继为起点，一直走到一个被修改点，那么走过的所有点（包括最后走的这个被修改点）将被缩为一点。

这样，每个操作块中我们仅需在一个有 $\mathcal{O}(\sqrt{n})$ 个点的图上操作。

修改时我们直接给涉及到的环打加法标记即可。

询问时我们对于每一个点，计算出在区间 $[l, r]$ 内的点权和以及点的个数并对后者乘上加法标记。

交换时直接交换即可。

如何维护一条链在区间 $[l, r]$ 内的点的个数呢？

直接维护时空都会炸，我们把这些询问离线下来，用类似归并的方法预处理即可。

代码实现

Ynoi 分块题

P5072 [Ynoi2015] 盼君勿忘 AC

考虑莫队。可以发现，在一个区间内，出现次数相同的数，贡献的系数是相同的。

比如在长度为 $len$ 的区间内 $x, y$ 均出现了 $z$ 次，那么他们的总贡献即为 $(x + y) \cdot (2^{len} - 2^{len - z})$ 。

那么我们可以对出现次数根号分治，如果出现次数不超过 $\sqrt{n}$ ，那么直接维护即可，否则在整个序列中出现次数大于 $\sqrt{n}$ 的数不会超过 $\sqrt{n}$ 个，对它们单独维护即可。

用快速幂会使时间复杂度多一个 $\log$ ，用光速幂即可。

代码实现

P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I AC

题解：

对序列分块，考虑维护以下几个量：

维护 $f_{i, j}$ 表示前 $i$ 个位置与第 $j$ 个块之间的逆序对个数（注意这里不考虑第 $j$ 个块内部的逆序对）。这个对整个序列和第 $j$ 个块排序，然后归并即可。
维护 $g_{i, j}$ 表示第 $i$ 个块和第 $j$ 个块之间的区间（包括这两块）内部的逆序对个数。这个有方程 $g_{i, j} = g_{i, j - 1} + g_{i + 1, j} - g_{i + 1, j - 1} + w_{i, j}$ 得到（ $w_{i, j}$ 表示第 $i$ 个块和第 $j$ 个块之间的逆序对数）。
维护 $pre_i$ 和 $suf_i$ ，前者表示序列的第 $i$ 个位置到其所在块的左端点的区间内部的逆序对个数，后者同理。这个用树状数组求即可。

询问时先通过 $pre_i$ 和 $suf_i$ 以及 $g_{i, j}$ 得到散块与整块内部的答案，在通过 $f_{i, j}$ 得到散块与整块之间的答案，最后在通过双指针得出两个散块之间的答案即可。

对于询问的 $l$ 和 $r$ 在同一个块内的情况，我们先令 $ans = pre_r - pre_{l - 1}$ ，剩下的问题就在于求出块的左端点到 $l - 1$ 以及 $l$ 到 $r$ 这两个区间之间的逆序对数，这个归并即可。

时空复杂度为 $\mathcal{O}(n\sqrt{n})$ 。

注意这题十分卡常！可以考虑以下几点：

把 $f_{i, j}$ 做二维前缀和，那么求散块与整块之间的贡献时就可以做到 $\mathcal{O}(1)$ 的时间复杂度。
做双指针时不一定要把两个序列都求出来，可以只求出一个数列，然后直接扫描另一个数列即可。

代码实现

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II AC

题解：

莫队二次离线的练手题。下面简单记录其思路。

直接做莫队必然要带 $\log$ ，而 $\log$ 的来源为 $\mathcal{O}(n \sqrt{n})$ 次地求一个子段 $[l, r]$ 内大于或小于某个 $a_i$ 的数的个数，显然这个询问具有差分性质，于是问题又变为求一个前缀 $[1, r]$ 内大于或小于某个 $a_i$ 的数的个数。

这样的话，我们可以对 $r$ 进行扫描线，然后就变成了 $\mathcal{O}(n)$ 次修改和 $\mathcal{O}(n\sqrt{n})$ 次询问，那么我们仅需用值域分块就可以做到 $\mathcal{O}(n\sqrt{n})$ 的时间复杂度。

然而这个算法的空间复杂度为 $\mathcal{O}(n\sqrt{n})$ ，考虑如何优化。

我们发现，在莫队指针移动的过程中有一些良好的性质，比如在执行 ++r 的移动时，左指针是始终不动的，同时这些指针的移动产生的若干询问中， $a_i$ 中的 $i$ 都等于 $r - 1$ 。

$a_i$ 在前缀 $[1, i - 1]$ 中的答案显然是可以预处理的，而对于剩下的部分，由于前缀 $[1, l - 1]$ 不变，且每次询问右指针移动的范围是一个区间，那么我们直接把这个区间挂在 $l - 1$ 上，在扫描线的过程中处理，这样就做到了 $\mathcal{O}(n)$ 的空间复杂度。

总的时间复杂度为 $\mathcal{O}(n\sqrt{n} + n \log_2 n)$ 。

代码实现

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III AC

题解：

先预处理出每一段整块的答案，然后把每个数所在的位置从小到大放到一个 $\texttt{vector}$ 内，询问时扫描散块中的每一个数的 $\texttt{vector}$ ，同时更新答案即可。

这个做法的空间复杂度为 $\mathcal{O}(n)$ 。

代码实现

P4688 [Ynoi2016] 掉进兔子洞 AC

题解：

发现求交集很难做，所以可以考虑用 $\texttt{bitset}$ 来维护。

离散化时，如果我们不执行 $\texttt{unique}$ 函数，那么莫队时，每一个数的每一次出现就都可以被 $\texttt{bitset}$ 上的每一位唯一表示，所以对于一个询问，直接将三个子段对应的 $\texttt{bitset}$ 取交集是没有问题的。

注意直接开 $\texttt{bitset}$ 空间会炸。我们将询问分成若干组，每组分别做莫队即可。

代码实现

P5356 [Ynoi2017] 由乃打扑克 AC

题解：

询问时只需在外层套一个二分，就可以转化为经典分块题。这个用分散层叠优化可以做到 $\mathcal{O}(n \sqrt{n \log_2 n})$ 的时间复杂度，并且是在线的。

当然由于这个问题本身是允许离线的，所以实际上还存在一种能够做到 $\mathcal{O}(n \sqrt{n \log_2 n})$ 的时间复杂度的做法。

设块长为 $m$ ，那么时间复杂度实际上是 $\mathcal{O}(nm + \dfrac{n^2 \log_2n}{m})$ 的，其瓶颈在于 $\mathcal{O}(\dfrac{n^2\log_2n}{m})$ 次的二分查找。分散层叠的做法是考虑优化单次询问内所有二分查找的总时间复杂度，我们不妨从另外一个角度入手 —— 优化单个块内所有二分查找的总时间复杂度。