Codeforces Round 762 (Div. 3)

E

E. MEX and Increments
题目大意
给你一个数组 $a$，数组整体求 $\text{mex}$，分别求出 $\text{mex} = \{0, 1, 2, \cdots, n\}$ 时候
需要修改几次 $a$ 数组？每一次修改操作定义为，将任意位置元素 $a_j \leftarrow a_j + 1$

分析 $\text{mex}$ 问题，一般是要翻译一下
不难想到对整个数组 $a$ 求一下 $cnt(a_i)$，即每个元素出现次数
$\text{mex} = x$，$\forall x \in [1\cdots n]$

• $\text{ans}(x)$ 有解的情况，当且仅当 $[0\cdots x-1]$ 所有数都要出现，此时 $cnt$ 对应的前缀和 $sum(x-1) \geqslant x$ 才有解
  进一步分析，因为只能 $a_j \leftarrow a_j + 1$，也就是说，令 $y$ 是 $[0\cdots x-1]$ 中空缺的数
  $y$ 只能由 $< y$ 的数来补全，必然有 $y < x$
  如果这些数连 $\text{mex} = x$ 的空缺都填不上，对于 $x+1, x+2, \cdots$ 更填不上了
  所以如果找到一个位置 $ans(x) = -1$，对于 $x+1, x+2, \cdots$，$ans$ 的值均为 $-1$
• 有解的话，可以考虑 $\text{dp}$，$dp(x)$ 表示 $\{0, 1, \cdots, x-1\}$ 全部都出现，所需要的代价
  $dp(0) = 0$，$\text{ans}(x) = dp(x) + cnt(x)$
  即在 $\{0, 1, \cdots , x-1\}$ 都出现的基础上，让 $x \leftarrow x + 1$，此时 $x$ 就不会出现
• 然后考虑 $dp(x) \to dp(x+1)$ 的转移，转移的代价就是需要补上空缺 $x$ 的代价
  如果 $cnt(x) = 0$，那么原序列就没有 $x$，那么需要找到 $y \in [0\cdots x-1]$ 这些数中，找到满足
  $cnt(y) \geqslant 2$ 的最大的那个数 $y$，这可以边扫描边维护一个栈实现
  栈中只保留 $cnt \geqslant 2$ 的数，如果找不到，那么 $ans(x+1, x+2, \cdots n) = -1$
  否则的话，$dp(x+1) = dp(x) + |x - y|$，并且要记得更新 $cnt(x)++, cnt(y)--$
• 如果 $cnt(x) > 0$，那么原序列已经有 $x$ 了，不需要额外补全元素，$dp(x+1) = dp(x)$
  记得如果 $cnt(x) \geqslant 2$ 的时候，将其放入栈中

一些区间有关的套路

多路归并

K 个最小和
给定 $k$ 个整数数组，包含 $k$ 个元素，在每一个数组中取出一个元素加起来，可以得到 $k^k$ 种不同的元素
求这些元素中最小的 $k$ 个值

先考虑下面的问题，合并两个长度为 $n$ 的数组 $A, B$，得到一个长度为 $n$ 的数组 $C$
合并的过程是任意取 $A, B$ 中的元素，可以得到 $n^2$ 个和，求这些和中最小的 $n$ 个，作为 $C$ 数组

首先先令 $A, B$ 均有序，实际上，对于有序数组，可以得到一张表

$$\begin{cases} A_1 + B_1 \leqslant A_1 + B_2 + \leqslant \cdots \leqslant A_1 + B_n \\ A_2 + B_1 \leqslant A_2 + B_2 + \leqslant \cdots \leqslant A_2 + B_n \\ \cdots \\ A_n + B_1 \leqslant A_n + B_2 + \leqslant \cdots \leqslant A_n + B_n \end{cases}$$

那么最小的一个元素，必然包含在 $\{A_1+B_1, A_2+B_1 + \cdots A_n+B_1\}$ 之中
考虑使用优先队列，维护一个二元组 $(sum, j)$，其中 $sum = A_i + B_j$
一开始的时候，对于每一个 $A_i, \ i \in [1, n]$，$(sum, b) \leftarrow (A_i+B_1, 1)$ 放入优先队列
然后动态地遍历 $j \in [1, n]$，每一次取堆顶元素 $C[j] \leftarrow \text{top}.sum$，$b \leftarrow \text{top}.b$
之后动态维护 $(sum, b) \longrightarrow (sum - B[b]+B[b+1], b+1)$

$k$ 路归并，实际上就是把之后的数组，合并到已经处理过的数组即可
另外需注意，假设我们检查了 $(A_i + B_j)$ 是第 $m$ 小，接下来要考虑 $(A_i + B_{j+1})$ 是不是第 $m+1$ 小
所以要维护一个 $B$ 相应的下标 $b$，因为 $B_{b+1}$ 可能作为要检查的候选值，放入优先队列中

动态连续和问题

UVA1400
给定一个数组 $D$，对 $m$ 个问询 $(a, b)$ 做出回答，需要找到 $a \leqslant x \leqslant y \leqslant b$ 的 $(x, y)$
使得 $D_x + D_{x+1} + \cdots + D_{y}$ 尽量大，如果有多组满足条件，那么 $x$ 尽量小，如果还有多解 $y$ 应尽量小

不难想到使用线段树，具体来说，对于某个节点 $p$，要维护的是
$pre$，表示 $p.l \leqslant pre \leqslant p.r$，并且 $S[p.l, pre]$ 区间和最大
换句话说，$pre$ 表示从 $p.l$ 往前最远能扩展到哪里
$suf$ 表示 $p.r$ 往左边最远能扩展到的位置，这里扩展的意思是，使得 $S[suf, p.r]$ 区间和最大
$sub$ 用一个二元组 $(x, y)$ 表示，满足 $p.l \leqslant x \leqslant y \leqslant p.r$ 并且 $S[x, y]$ 最大

维护好这些信息之后，考虑 $\textbf{pull}$ 操作，不妨设 $p$ 的两个子节点分别为 $pl, pr$
根据题目要求，定义一个 $\max(seg1, seg2)$ 操作，如果 $S(seg1) \neq S(seg2)$，那么取区间和 $S$ 较大的那一段
否则如果 $seg1.x \neq seg2.x$，取 $x$ 较小的，$x$ 仍然相同的话，取 $y$ 较小的

• 对于 $p.pre$，如果 $S[pl.l, pl.pre] \geqslant S[pl.l, pr.pre]$，那么 $p.pre \leftarrow pl.pre$
  否则的话，$p.pre \leftarrow pr.pre$
• 对于 $p.suf$，如果 $S[pr.suf, pr.r] > S[pl.suf, pr.r]$，（因为如果相等的话，要取尽量靠左的），$p.suf \leftarrow pr.suf$
  否则的话，如果有 $S[pl.suf, pr.r] \geqslant S[pr.suf, pr.r]$，$p.suf \leftarrow pl.suf$
• 接下来考虑 $p.sub$ 对应的二元组如何求，实际上，$p.sub$ 是以下几段的最大值
  $\max\{\quad [pl.sub.x], [pr.sub],[pl.suf \cdots pr.pre] \quad\}$
  用上面定义个 $\text{max}$ 操作，求出最大的区间 $[x, y]$ 即可

下面考虑问询 $(a, b)$
如果找到了 $(a, b)$ 对应的区间 $p$，直接返回 $p.sub$
没找到的话，如果 $b \leqslant p.\text{mid}$，只需要递归左子区间，$a > p.\text{mid}$，只需要右子区间
否则同时递归左子区间和右子区间，答案有三段构成
$\max\{ [pl.sub], [pr.sub], [pl.suf, pr.pre] \}$，其中 $pl.sub$ 和 $pr.sub$ 都可以直接通过递归来返回
递归若返回的是区间 $[x, y]$，如何获取 $suf, pre$ 等信息？
这里我们令递归返回的是 $\textbf{node}$ 结点，如果同时递归左右子树，那么就新开一个结点 $tmp$
结点的 $sub, pre, suf$ 信息按照如上所述更新即可，返回 $tmp$
具体来说可以复用 $tmp \leftarrow \textbf{pull}(\text{node(l)}, \text{node(r)})$ 函数
按照之前定义的 $\textbf{pull}$ 规则来合并左右子节点，并返回

滑动窗口杂题

最小覆盖子串

这是一个连续字串的问题，很自然地想到滑动窗口
不难想到，用 $\textbf{cnt}$ 这个 $\text{map}$ 来维护滑动窗口中字符出现的次数
用 $\text{mp}$ 预处理出 $T$ 中字符出现的次数，那么就可以写出 $\text{check}()$ 函数了

首先能想到的思路是，一开始令两个指针 $i = 0, j = 0$，滑动窗口为 $[i, j]$
遍历 $i \in [0, n）$，对每一个 $i$，令 $j \leftarrow i$
$\textbf{while} \ \text{check()} = \text{false}$，那么就令 $j\leftarrow j+1$，同时更新 $\textbf{cnt}$
这样当 $\textbf{while}$ 循环执行完之后，$[i, j]$ 就是满足条件的，用来更新答案即可
下面问题来了，$j$ 确定下来了，$i$ 接下来要怎么走？$i = i+1, i+2, \cdots$
这样对于每一个 $j$，当 $i$ 处出现冗余的时候，$[i, i+1, \cdots, j-1]$ 这么多可能都是冗余的，这样时间复杂度是 $O(n^2)$ 的

所以要换一个思路，产生上述情况的原因是
$[i, i+1, i+2, \cdots)$ 一定缺少了某个元素，这个元素在 $j$ 处才被找到
此时 $[i, i+1, i+2, \cdots)$ 可能会出现冗余元素，基于此，可以设计出如下算法
开始时令 $i = 0, j = 0$，并且 $i$ 先不去动它，令 $j \in [0, n)$ 遍历
$\textbf{while} \ \text{check}() = 1$，就说明 $[i, j]$ 合法，先更新答案，然后不断删除 $i$ 开始的前缀冗余元素
$i \leftarrow i+1$，同时更新 $\textbf{cnt}$，这样当 $\textbf{while}$ 循环结束之后
$[i, j]$ 又变成了删除冗余元素之后，不满足条件的区间，$j$ 又可以接着往前走了
这样不仅不会漏解，时间复杂度还可以保证是 $O(n)$ 的

唯一的雪花
给定一个序列 $A$，找一个尽量长的连续子序列 $A[l, r]$，使得序列中没有相同元素
这个问题和之前的问题的区别在于，这一次是尽量长

不难想到用滑动窗口，并且用一个 $\textbf{set}$ 维护滑动窗口中的元素
开始时候令 $i = 0, j = 0$，先不去动 $i$，那么 $j$ 能往前走的充要条件是，$\textbf{set}(A_j) = \emptyset$
题中要求尽量长，对于起点在 $i$ 位置的窗口，先不去动 $i$，用一个 $\textbf{while}$ 循环
只要 $\textbf{set}(A_j) = \emptyset$，就把 $A_j$ 放入集合中，并且令 $j$ 往前走
这样 $\textbf{while}$ 循环结束后，$[i, j)$ 就是以 $i$ 作为起点，最长的满足条件的滑动窗口，用 $j-i$ 更新答案

接下来呢？ $i \leftarrow i+1$ 往前走，同时维护 $\textbf{set}$ 删除 $A_i$，相当于更新窗口起点
重复以上算法即可，因为 $[i, j)$ 没有冗余元素，$[i+1, j)$ 也不会有冗余元素，所以 $i$ 一定在 $j$ 后面
扫描的时间复杂度是 $O(n)$，加上 $\textbf{set}$ 的维护，总时间复杂度是 $O(n\log n)$

shuffle的播放记录
播放器中有 $s$ 首歌，一开始这些歌会随机排序，全部播放完之后再随机排序，给出一个长度为 $n$ 的播放记录 $x_i$
不一定从最开始记录，其中 $1 \leqslant x_i \leqslant s$，那么请问下一次随机排序发生的位置有多少种可能？
就是问，下一次随机排序的位置，可能是 $[1, 2, \cdots, s]$，这中间有几种是合法的呢？

这是一个确定窗口长度的滑动窗口问题，滑动窗口位置为 $[i, i+s-1]$，不难想到如下动态维护的算法
用 $tot$ 维护滑动窗口中有几个不同的元素，这样窗口滑动的时候，维护过程如下
$\textbf{if}\ --\text{cnt}(A_i) = 0$，$tot--$， $\textbf{if} \ ++\text{cnt}(A_{i+s}) = 1$， $tot++$， $\textbf{then}\ i++$

那么算法大致执行流程如下，枚举随机播放的位置，$i \in [0, s-1]$，作为滑动窗口的起点
通过预处理判断每一个位置是否是合法起点，$i$ 能成为答案的充要条件是
$\{i, i+s, i+2s, \cdots \}$ 都是滑动窗口的合法起点
预处理判断的过程也很简单，检查序列位置 $[i, i+s-1]$，如果此时滑动窗口的 $tot = s$，$i$ 就是合法起点

算法的主过程大致如此，问题是，可能存在不完整的窗口，怎么办呢？可以在序列前后补 $0$
$[0\cdots s-1] \cup [s\cdots s+n-1] \cup [s+n \cdots n+2s-1]$
这样把原序列放在 $[s\cdots s+n-1]$ 中，前后补 $0$，滑动窗口的起点从 $0$ 开始，为了处理边界，加入哨兵结点
也就是说，一开始的时候滑动窗口在 $[0, s-1]$ 这个位置，此时 $tot = 0$，滑动窗口还没有开始检查序列
此时状态也被认为是合法状态，对于不完整的段
$i \leqslant s-1$，如果此时 $(i+s-1)-s+1 = tot$，那么 $i$ 合法
$i+s-1 \geqslant s+n$，如果此时 $s+n-1-(i)+1 = tot$，那么 $i$ 合法
因为加入了补 $0$ 的段，窗口滑动的时候，注意 $\textbf{if} \ A_i \neq 0$ 才执行 $--\text{cnt}(A_i) = 0$ 的判断

另外注意特判，$s \geqslant n+1$，此时播放记录中的 $n$ 首歌，只是所有歌单 $s$ 中的一段，不是完整的歌单
那么下一次随机播放的位置，可以是 $s$ 首歌单中的任意一首，答案为 $s$

单调性优化杂题

防线
给定一个长度为 $n$ 的序列，删除一个连续子序列，使得剩下的序列中有一个长度最大的，连续的，严格递增的子序列
换句话说，就是要在 $A$ 中找到 $[i, j]$，$i$ 往左扩展得到最长的连续递减序列长度为 $dp1(i)$
$j$ 往右扩展得到最长的连续递增序列长度为 $dp2(j)$，我们要找到 $dp1(i) + dp2(j)$ 最大

首先，令 $dp1(i)$ 表示以 $i$ 结尾的最长连续递增序列的长度
$dp2(i)$ 表示从 $i$ 开始，以 $i$ 起始的最长连续递增序列的长度，这都可以通过扫描预处理得到

对于某一个 $i$，$i \in [1, n]$，先固定 $i$ 不动，对于此时的 $dp2(i)$
要从已扫描过的序列 $j \in [1, i-1]$ 中找到 $dp1(j)$ 最大的，即 $\displaystyle\max_{j \in [1, i-1]} dp1(j)$，此外还要保证 $A_j < A_i$

$\left(\displaystyle\max_{j \in [1, i-1]} dp1(j)\right)$ 第一反应是用单调栈维护
但很可惜这里不能单调栈，原因是我们需要的答案是 $\displaystyle\max_{i} \left(dp2(i) + \max_{j \in [1, i-1]} dp1(j) \Big| \{A_j < A_i\}\right)$

如果用严格单调递增的栈来维护 $\displaystyle\max_{j \in [1, i-1]} dp1(j)$，对于 $i$，将 $dp1(i)$ 入栈之前
我们需要扔掉栈中满足 $x \geqslant dp1(i)$ 的元素，
而这些元素很可能会和 $dp2(i+1, i+2, \cdots)$ 构成更优解，但我们把它扔掉了，就丢失了最优解

那我们不要把它扔掉不就可以了？
对于 $j \in [1, i-1]$，一定是 $dp1(j)$ 越大越好，同时 $A(j)$ 越小越好
基于此来优化，对于 $dp1(j1) < dp1(j2)$ 并且 $A(j1) \geqslant A(j2)$，$j1$ 是无用解

那么候选集合 $j \in [1, i-1]$ 一定是

$$\begin{cases} &A(j1) < A(j2) < \cdots < A(jk) \\ &dp1(j1) < dp1(j2) < \cdots < dp1(jk) \end{cases}$$

那问题就简单了，用一个 $\textbf{set}$ 维护二元组 $(A(j), dp1(j))$，按 $A(j)$ 排序
对于每一个位置 $i$，$dp1(j), j \in [1, i-1]$ 最大的位置，一定是最右边的满足 $A(j) < A(i)$ 的位置
可以在 $\textbf{set}$ 中二分查找到这个位置 $k$，然后用 $dp1(k) + dp2(i)$ 来更新答案

接下来考虑如何去维护？ 假设当前的二元组为 $cur = (A(i), dp1(i))$，$cur$ 按道理说应该插入 $\textbf{set}$ 中 $k+1$ 处
根据上面分析，如果 $dp1(\textbf{set}(k)) \geqslant dp1(i)$，那么 $cur$ 不应该插入 $k+1$ 处

否则的话，在 $\textbf{set}$ 中插入 $\text{cur} = (A(i), dp1(i))$，插入的时候注意判断一下
如果 $\textbf{set}$ 中有第一关键字等于 $A(i)$ 的元素，就把它删掉，保证候选集合中 $A$ 是严格单调的
然后找到 $cur$ 在 $\textbf{set}$ 中的位置 $p$，检查 $p' = (p+1, p+2, \cdots )$
如果 $A(\textbf{set}(p')) > A(cur)$ 并且 $dp1(\textbf{set}(p')) \leqslant dp1(cur)$
就在 $\textbf{set}$ 中删掉 $p'$

裁剪序列
题目大意，给定一个长度为 $n$ 的序列 $a$，将其分为若干段，满足每一段所有数的和 $\leqslant M$
还要满足取每一段所有数的最大值，然后这些最大值求和，要使得这些最大值之和最小

考虑 $dp$，用 $dp(i)$ 表示 $[1\cdots i]$ 这些数分成若干段，满足每一段的和 $\leqslant M$ 并且
每一段数的最大值的和能取到的最小值，状态转移方程如下

$$dp(i) = \min_{1 \leqslant j < i} \left(dp(j) + \left(\max_{k \in [j+1, i]}A_k \right)\Big| \left\{\sum_{k \in [j+1, i]} A_k \leqslant M\right\}\right)$$

本例的限制条件为 $\displaystyle\sum_{k \in [j+1, i]}A_k \leqslant M$，并且要取 $[j+1, i]$ 区间内的最大值 $\max A_k$
那么能够成为候选值的 $A_j$ 一般是有单调性的

• 因为 $\max_{k \in [j+1, i]} A_k$ 非负，所以 $dp(j)$ 非严格单调递增，也就是说，如果要让 $dp(j)$ 尽量小的话
  $j$ 应该要尽可能靠左，也就是说，满足 $\sum [j, i] \leqslant M$ 的最左边的那个 $j$，对应的 $dp(j-1)$ 是满足条件最小的 $dp$ 值
  首先有取值 $dp(i) \leftarrow dp(j-1) + \max A[j, i]$
• 我们需要的是 $\min\left(dp(j) + \displaystyle\max A[j+1, i]\right)$，这部分的值没有单调性
  $dp(j)$ 最小并不能够使得 $dp(j)+ A_k$ 最小，考虑 $dp$ 增大，$A_k$ 减小的时候，值也会动态变化
  在找到 $\sum[j, i] \leqslant M$ 这个约束条件之后，还要用二叉堆维护可能的候选值 $\{j, j+1, \cdots, i\}$，
  可能的候选值是如何变化的呢？
  不难发现，$\sum [j, i] \leqslant M$，对于某一个 $i$ 而言，$j$ 一定越靠近 $i$ 越好，同时 $A_j$ 越大越好
  $j1 < j2$，如果 $A(j1) \leqslant A(j2)$，那么 $j1$ 就是无用的解

$$\begin{cases} &j1 < j2 < \cdots < jk \\ &A(j1) > A(j2) > \cdots > A(jk) \\ &\text{dp}(j) \text{非严格单调增} \end{cases}$$

基于以上分析，可以设计出如下算法，对于当前的 $i$
用单调队列维护动态变化的候选值 $A_j$，$A_j$ 的意义是，存在 $[p, i]$ 区间以 $A_j$ 作为最大值，$p$ 应该取多少？
应该使得 $dp(p)$ 越小越好，即满足约束条件的情况下，$p$ 尽量靠左
不妨设左边第一个比 $A_j$ 大的元素位置是 $le(j)$，那么 $p = \text{le}(j) + 1$
实际上，单调队列维护的候选值 $\{j1, j2, \cdots, jk\}$，左边第一个比 $A(j2)$ 大的元素就是 $A(j1)$，以此类推
所以 $j2$ 在二叉堆中对应的值为 $dp(j1) + \max A[j1+1 \cdots i-1] = dp(j1) + A(j2)$
注意，根据以上分析，$A[j1+1\cdots i-1]$ 都是以 $A(j2)$ 作为最大值的

我们要在单调队列中插入 $A(i)$，首先维护队尾元素的单调性
$\text{que}[\cdots, r3, r2, r1]$，我们有 $A(\text{que}[r3]) > A(\text{que}[r2]) > A(\text{que}[r1])$
如果 $\text{que}[r1] \leqslant A(i)$，那么要删除 $\text{que}[r1]$，这个元素在二叉堆中对应的值为
$dp(\text{que}[r2]) + \max A(\text{que}[r2]+1, \cdots i-1) = dp(\text{que}[r2]) + A[\text{que}[r1]]$，也要相应地删掉

然后尝试加入 $A(i)$，同时在二叉堆中加入 $dp(\text{que}[r]) + \max A[\text{que}[r]+1 \cdots i] = dp(\text{que}[r]) + A(i)$
这样就完成了维护

这样我们就维护出了 $dp(j)$ 动态增加，$A_k$ 动态减少时候的最小值，取二叉堆堆顶元素即可
二叉堆维护的是动态变化时候，可能的 $A_k$ 值，我们还需要知道 $dp(j)$ 最小可能取多少？
考虑限制条件
用一个滑动窗口，维护最左边满足 $\sum A[p\cdots i] \leqslant M$ 的 $p$ 值，此时
$dp(i) = \min(dp(i), dp(p-1) + \max A[p\cdots i])$ 对应的 $dp(p-1)$ 是满足约束条件的最小值

另外，考虑限制，需要检查一下队首元素 $\text{que}[l1, l2, \cdots]$
如果 $\text{que}[l] < p$，那么需要删除 $\text{que}[l]$，
同时，二叉堆中对应的 $dp(\text{que}[l1]) + \max A[\text{que}[l1]+1 \cdots i] = dp(\text{que}[l1]) + A(\text{que}[l2])$ 取不到了
也对应地删除，另外不难发现，此时 $\max A[p\cdots i]$ 就是我们维护的 $\text{que}[l]$
这里取 $dp[i] \leftarrow \min(dp(p-1) + \text{que}[l], \ \text{二叉堆的最小值})$ 就是答案