Gym103687D The Profiteer：回滚莫队信息双指针可以做到线性对数

标题写得好

所谓的回滚莫队信息意思是，设信息保存在两个大小分别为 \(a, b\) 的结构上，将这两个信息进行合并得到大小为 \(a + b\) 的信息需要的时间为 \(\Omega(\min\{a, b\}\cdot f(n))\)；而给定一个大小为 \(1\) 的信息，可以在 \(\mathrm O(f(n))\) 时间内将它加入到任何一个结构中，得到新的结构的信息。换句话说，这是一种可以支持加入，但是不支持合并（合并开销不如一个一个加入）的信息。一个例子是颜色出现个数的最大值（《历史的研究》），另一个例子是 \(m = \Omega(n)\) 条件下的背包问题（例题）。

双指针的意思是：给定一个序列长度为 \(n\)，对于每一个 \(l\in[1, n]\)，我希望求出第一个 \(r\ge l\) 使得区间 \([l, r]\) 的信息具有某种特性，记这个问题的答案为 \(f(l)\)。保证 \(\forall l_1 < l_2\)，有 \(f(l_1)\le f(l_2)\)，也就是问题的答案单调上升。对于莫队信息（支持删除），我们有尺取法可以在 \(\mathrm O(n)\) 时间复杂度内解决这个问题（以下假设信息合并时间为 \(\mathrm O(1)\)）；对于支持快速合并但是不能删除的信息，我们有 baka's trick 即双栈法可以在同样时间复杂度下解决问题。现在，对于回滚莫队信息，快速解决双指针问题，也可以做到吗？

首先回顾回滚莫队，它可以解决给出序列上 \(m\) 个区间，要求询问区间内回滚莫队信息的问题，时间复杂度为 \(\mathrm O(n\sqrt{m})\)。即使询问区间满足左右端点单调性相同，上述问题也只能做到 \(\Omega(n\sqrt{m})\)。以相似的思路，我们对于双指针问题很容易基于分块给出 \(\mathrm O(n^{1.5})\) 的做法。那么存在更优做法吗？

对于序列进行整体二分。设当前状态为 \((l, r, L, R, X)\)，表示求解区间 \([l, r]\) 内所有 \(f(i)\)，并且已知它们的范围是 \([L, R]\)。\(X\) 表示区间外信息，即若 \(r < L - 1\) 则 \(X\) 表示区间 \([r+1, L-1]\) 的信息。接下来，考虑取 \(P = \lfloor\dfrac{L+R}2\rfloor\)。我们需要找到一个最大的 \(p\in[l, r]\)，使得 \(f(p)\le P\)。那么直接枚举即可，分治层数是 \(\mathrm O(\log n)\)，每一层的 \([l, r]\) 和 \([L, R]\) 都不交，所以总复杂度是 \(\Theta(n \log n)\)。

未完待续。