时隔两年。

lzyqwq · 2025-11-06 20:17:38 · 题解

大家好，我喜欢暴力数据结构，于是使用分块 AC 了此题。

给出 n 个点 (x_i,y_i)，保证 x_i,y_i 互不相同。求有多少个二元组 (i,j)，满足 x_i<x_j\land y_i<y_j 且不存在 k 使得 x_i<x_k<x_j\land y_i<y_k<y_j。

先离散化。这样横纵坐标都变成 1\sim n 的排列。因此相当于平面上有 n 个点 (i,p_i)。

那么 (i,j) 这个二元组合法，当且仅当：

对于一个 i，记能与其产生贡献的 j 从小到大依次为 w_1,\dots,w_m。记 S 为 p_j>p_i 的 i 构成的集合。容易发现：

• 对于 2\le u\le m，w_u 是 S 中最小的 j，使得 j>w_{u-1}\land p_{j}<p_{w_{u-1}}。

可以先证明 w 中的点都能与 i 产生贡献，再证明不在 w 中的点都不能与 i 产生贡献。这个结合偏序关系很容易得出。

这启示我们按照 p_i 从大到小扫，同时维护 S。记 \text{nxt}_i 为最小的 j 使得 j>i\land p_j>p_i，这个单调栈扫一遍即可。由于扫到 p_i 时，\text{nxt}_i 一定被加入 S 中。所以 w_1=\text{nxt}_i。再记 q_i 表示 S 中最小的 j 使得 j>i\land p_j<p_i。考虑这样一个暴力：从 j=\text{nxt}_i 开始，检查是否合法，再 j\leftarrow q_j。

考虑优化，很难不想到弹飞绵羊。以 B=\mathcal{O}(\sqrt n) 为块长分块。维护 f_i,g_i 表示从 i 开始跳出所在块到达的位置和跳的次数（包含 i 但不包含 f_i）。那么对于每个点就从 j=\text{nxt}_i 开始，每次令答案加上 g_j，再令 j\leftarrow f_j。

考虑向 S 中加入 i 后会带来怎样的影响。首先是对 q 的影响，相当于区间 [1,i-1] 内的 q_j 要对 i 取 \min。对于 i 所在块内的 f,g，直接重构即可，倒着扫这个块，每个 j 的信息从 q_j 转移。块内每个点需要单点查询 q，总共 \mathcal{O}(n\sqrt n) 次。因此用一个 \mathcal{O}(\sqrt n)-\mathcal{O}(1) 的分块维护 q。i 右边的块的 f,g 不受影响。至于 i 左边的块，可以发现块中的位置在块内跳的过程是不受影响的，跳出块这一步会受到 i 的影响，因此是 f 数组区间对 i 取 \min，g 不受影响。同样使用 \mathcal{O}(\sqrt n)-\mathcal{O}(1) 的分块维护。

时间复杂度 \mathcal{O}(n\sqrt n)，空间复杂度 \mathcal{O}(n)。

闲话：上一次见到这个题是在 2023 年的 xyd 模拟赛，当时完全没思路。现在还是不会 polylog 做法。不同的是当时一切仍未开始，现在一切已经结束。人生有梦，各自精彩。