P8349 [SDOI/SXOI2022] 整数序列 解题报告

P8349 [SDOI/SXOI2022] 整数序列 解题报告：

更好的阅读体验

题意

给定序列 \(a,b\)，\(q\) 次询问两种颜色 \((x,y)\)，定义一个区间的权值为其中 \(a\) 值为 \(x\) 或 \(y\) 的 \(b\) 值之和，求 \(x\) 数量等于 \(y\) 数量的子区间权值最大值。

\(1\leqslant n\leqslant 3\times 10^5,1\leqslant q\leqslant 10^7,\text{7s}\)。

分析

轻视了这道题啊。

考虑根号分治，令阈值为 \(S\)。

小集合对小集合直接把位置归并成一个序列暴力扫一遍即可，大集合对大集合可以直接暴力+记忆化，这里的复杂度是 \(O(qS+\frac{n^2}{S})\)。

难点主要是小集合对大集合（令 \(x\) 为小集合，\(y\) 为大集合），我们发现我们将 \(x\) 和 \(y\) 对应位置取出来之后，对于一个 \(y\) 连续段，只要其长度大到没有合法子区间能跨越它，那么它的长度就是无关紧要的了，可以缩到恰好满足条件的长度。

更具体地说，我们维护一个 \(y\) 坐标集合，对于每个长度为 \(x\) 的连续段，都向前找 \(x+1\) 个没加入集合的 \(y\) 加入集合，向后找 \(x+1\) 个没加入集合的 \(y\) 加入集合，那么保留集合内的 \(y\) 与 \(x\) 进行运算也能保证答案的正确性。

而这样得到的集合大小是不超过 \(2S\) 的，那么我们得到了一个 \(O(qS\log n+\frac{n^2}{S})\) 的做法，令 \(S=\frac{n}{\sqrt{q\log n}}\) 就是 \(O(n\sqrt{q\log n})\) 了。

实际上这个 \(\log\) 可以去掉。我们离线，把询问挂在对应大集合上。

扫两遍，分开维护向左取的 \(y\) 和向右取的 \(y\)，每次用一个栈维护若干个连续的连续段集合，判断新加入的集合能否和栈顶合并显然可以 \(O(1)\)。最后我们将每个连续段内部的 \(y\) 以及其向左（或向右）还能扩展的 \(y\) 加入集合即可。

这样的复杂度就是 \(O(qS+\frac{n^2}{S})\) 了，令 \(S=\frac{n}{\sqrt q}\) 即可得到 \(O(n\sqrt q)\) 的复杂度。

代码

#include
#include
#include
#include
#include