[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)\)。但这不够一般化，还需要进一步转化。

\(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\))。