自动搬运

查看原文

来自洛谷，原作者为

	zhouhuanyi 在量子世界中，所有的未来都同样真实。

搬运于2025-08-24 22:34:09，当前版本为作者最后更新于2023-12-14 12:27:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原问题比较类似 $\text{ZJOI 2020}$ 序列，可以划归为一个线性规划的形式，考虑将线性规划对偶，不难发现等价于求一个序列 $b$，使得对于任意 $1\leqslant l\leqslant r\leqslant n,r-l+1\leqslant m$ 均满足 $\sum_{i=l}^{r}b_{i}\leqslant 1$，最大化 $\sum_{i=1}^{n}a_{i}b_{i}$。

和 $\text{ZJOI 2020}$ 序列类似的，手玩一下可以发现 $b$ 只有 $-1,0,1$ 三种取值，不妨把 $0$ 剔除，只考虑 $1$ 与 $-1$，不难发现则两个距离 $< m$ 的 $1$ 不能相邻，而此时也一定合法，因为每两个 $<m$ 的 $1$ 之间都至少有一个 $-1$，则选一个长不超过 $m$ 的序列的最大值即使最优也一定是 $1,-1$ 的交错序列，这个一定是 $\leqslant 1$ 。而此时由于要最大化，我们取 $1$ 很可能最优，而对于两个距离 $<m$ 的 $1$，中间必然要至少一个 $-1$，而由于要最大化，我们只取一个 $-1$ 即可。

现在相当于要选择若干个位置，加上权值，如果选择的相邻两个位置距离 $<m$，则要减去中间的最小值，不难使用 $\text{dp}$，做到 $O(nq)$。但这不够一般化，还需要进一步转化。

$m=n$ 时的答案是平凡的，就是 $a_{1}+\sum_{i=2}^{n}\max(a_{i}-a_{i-1},0)$，这启发我们将其划归为若干个该种问题的组合，可以发现其实对于相邻两个 $1$ 一定要 $\geqslant m$ 的限制将其拆分为若干个段，每个段之间的距离 $\geqslant m$，那么我们只需要考虑那些元素成为了新划分的段的端点即可。一个元素 $[l+m,r]$ 的元素 $i$ 被划分为出来会导致 $a_{i}-\sum_{j=i-m+1}^{i}\max(a_{j}-a_{j-1},0)$ 的增加量，要求所有距离 $<m$ 的不能被同时选中，特别的我们钦定 $i$ 不能为 $l+m-1$，因为它的贡献不太一样而且不会被选中，因为如果这样我们将其挪到前面一定更优。

现在相当于这样一个问题，$q$ 组询问，每次询问一个区间 $[l,r]$，求在 $[l,r]$ 中选择若干个元素，使得所有元素的距离 $\geqslant m$，最大化所选元素的权值和。

$m$ 很小的情况是平凡的，直接分治可以 $O(nm \log n)$，关键在于 $m$ 很大的情况。关于距离的问题可以联想到一个结论，如果将一个序列中所有距离为 $x$ 或 $y$ 的连边，则得到的图为类平面图，$\text{seperator}$ 也是 $\sqrt n$ 级别的。在一些这样的平面图或类平面图上面查最短路是可以 $O(q\sqrt n)$ 与 $O(q\sqrt n\log n)$ 的，在上面独立集计数与匹配计数时可以 $O(2^{\sqrt{2n}})$ 与 $O(2^{\sqrt{n}})$ 的。这启发我们将其变为一个类平面图的最短路问题。

不难发现这样的小的 $\text{seperator}$ 实际上是可以被找到的，当 $m$ 很小的时候显然，如果将所有数事先对 $0$ 取 $\text{max}$，则选择的相邻的两个数的距离不会超过 $2m$，则我们找到了一组 $O(m)$ 的 $\text{seperator}$。而当 $m$ 很大的时候，网格划归后相当于求一个 $\lceil \frac{n}{m} \rceil+1$ 行 $m$ 列的网格图只能往右或下走的最长路问题，特别的，如果走到了右边界可以悬空一行在挪至左边界，不过这意味着其至少经过了一个右边界，直接取所有右边界即构成了一组 $O(\frac{n}{m})$ 的 $\text{seperator}$，可以把这个 $\text{case}$ 判掉。此时由于网格图的性质，我们总能找到一个 $O(\sqrt n)$ 的 $\text{seperator}$，迭代做即可。

如果按照 $m$ 与 $\sqrt n$ 的大小关系根号分治，则我们每次都可以找到一个 $O(\sqrt n)$ 的 $\text{seperator}$，由 $T_{1}(n)=2T_{1}(\frac{n}{2})+O(n\sqrt n)$ 与 $T_{2}(n)=T_{2}(\frac{n}{2})+O(q\sqrt n)$，用主定理可得复杂度为 $O((n+q)\sqrt n$)。