[Ynoi2005] qwq

· · 题解

原问题比较类似 \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)。但这不够一般化，还需要进一步转化。

现在相当于这样一个问题，$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$)。