U646757 题解

wdsqwq · 2026-01-02 18:35:15 · 个人记录

考虑操作分块，每 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) 。我们有经典结论：

• 结论一：满足 (\max\limits_{i=l+1}^{r-1}a_i)<\min(a_l,a_r) 的 (l,r) 对数为 O(n) 对。

定义 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 ，那么我们大胆一点，给出结论：

• 结论二：满足 (\max\limits_{i=l+1}^{r-1}a_i)<\min(a_l,a_r) 的 (l,r) 点对和所有 l_i\neq\varnothing,r_i\neq\varnothing 的 (l_i,r_i) 点对一一对应构成双射。

证明略。

那么这样子咱们就可以快速找出全局或区间内的支配点对了，定义 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) 点对一共只有 O(B) 个。

• 证明：定义 sum_i=\sum\limits_{j=L_i}^{R_i}a_j ，满足要求的 (bel_l,bel_r) 必满足 \sum\limits_{j=bel_l+1}^{bel_r-1}(sum_j)<\min(sum_{bel_l},sum_{bel_r}) ，这样子就可以用结论一进行论证结论三。

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

• 结论四：(l,r)(bel_l\neq bel_r) 合法的必要不充分条件是 (\sum\limits_{j=l+1}^{R_{bel_l}}a_j)<a_l 且 (\sum\limits_{j=L_{bel_r}}^{r-1}a_j)<a_r 。

• 结论五：对于同一个块中，满足结论四中讲述的任意一个条件的 i 共 O(\log V) 个。

• 结论六：对于大部分的支配点对，它们都满足在修改前也是支配点对，不满足的只有每个块 O(1) 个，且可以 O(1) 找出这些不满足的点对。

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

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

• 结论七：r-l\ge 3 时，如果 (l,r) 是支配点对，它一定在修改前也是支配点对。证明略。这部分所覆盖的面积可以 O(\frac{n^2}{B}+nf(\frac{n}{B},B)) 算出来，具体的方法是整体分块，大量分块科技处理，其中 f(n,m)\gets O(\frac{n^2m^2}{B^2B_2^2w}+\frac{B^2B_2^2}{w}+mB_2) ，其中 B\gets \sqrt{n},B_2\gets \sqrt{m} 。

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