U646757 题解

$\color{black}{*25}\color{red}{6768}$ .

$\color{black}{*179}\color{red}{2364}$ .

考虑操作分块，每 $O(B)$ 个操作分一个块，定义 $Q'_i$ 为第 $i$ 个操作所在块， $W_i$ 为第 $i$ 个块中第一个操作的编号， $E_i$ 为第 $i$ 个块中最后一个操作的编号。

枚举 $i\in [1,Q'_Q]$ ，定义 $S\gets \{1,N+1\}+\sum\limits_{j=W_i}^{E_i}\{L_j,R_j+1\}$ ，将 $S$ 去重并排序，得到 $S'$ 。

现在我们定义 $bel_i=\max\limits_{1\le j\le (|S'|-1),S'_j\le i}(j)$ 。

回想一下原题（P9530）的思路，我们需要求出一类支配点对，并求出它们的覆盖集大小，这些支配点对形如 $(l,r)(r-l\ge 2)$ ，需要满足的条件是 $(\sum\limits_{i=l+1}^{r-1}a_i)<\min(a_l,a_r)$ ，容易发现满足该条件的必要不充分条件是 $(\max\limits_{i=l+1}^{r-1}a_i)<\min(a_l,a_r)$ 。我们有经典结论：

定义 $l_i=\max\limits_{j<i,a_j>a_i}(j),r_i=\min\limits_{j>i,a_j>a_i}(j)$

我们考虑对于每个支配点对 $(l,r)$，令 $w\gets \argmax\limits_{i=l+1}^{r-1}(a_i)$ ，容易发现 $l=l_w,r=r_w$ ，那么我们大胆一点，给出结论：

证明略。

那么这样子咱们就可以快速找出全局或区间内的支配点对了，定义 $L_i=S'_i,R_i=S'_{i+1}-1$ 。

那么现在支配点对分为 $bel_l\neq bel_r$ 的和 $bel_l=bel_r$ 的。

考虑先做 $bel_l\neq bel_r$ 的部分，我们有一个结论：

还是运用结论二找出可能的 $(bel_l,bel_r)$ 点对，对于这部分内部具体的点对如何寻找，我们还有结论：

对于每一个可能的 $(bel_l,bel_r)$ ，可以在 $O(\log V)$ 的时间内用基数排序大力做完寻找支配点对的部分。

对于 $bel_l=bel_r$ 的部分，我们还有结论：

结合各部分，这题就做完了，复杂度 $O(\frac{n^2}{B}+nB\log V)$ ，$B$ 取 $O(\sqrt{\frac{n}{\log V}})$ 时最优，复杂度是 $O(n\sqrt{n\log V})$ 。