题解：P6579 [Ynoi2019] Happy Sugar Life

· · 题解

我们要计算两个点 A,B 都在某个矩阵 R 当中的顺序对数目（A\leq B）。

首先我们放弱条件，如果我们只要求 B\in R。容易 O(n\log n) 计算每个点为 B 的顺序对个数 c_i。我们相当于计算这个矩形里面所有点的 c 的和。这是经典二位数点，还是 O(n\log n) 的。

考虑我们现在加上 A\in R 这个条件。我们把平面分为四个部分。

由于 B\in R，所以 A 只能属于这四部分。我们要计算 A 在第 4 部分的答案。反面考虑，计算 A 在 1,2,3 部分的答案的和。

首先在 1 部分。那么任意一个 B\in R 都构成顺序对关系。直接二位数点即可。

然后 2,3 类是等价的。以第 3 类为例子。我们即计算下面的 (A,B) 对数量：

对序列分块。把答案分为 A,B 在同个块或者在不同块。如果 A,B 在同一个块。那么本质不同的询问数是 O(B^2) 的，容易二维前缀和直接预处理。

否则如果 A,B 在不同块。每个询问从小到大扫每个块。记录之前有多少个点在 3 部分。然后乘上这个块有多少在 4 部分即可。

复杂度 O(n\sqrt n)。截至 2025 年 5 月 12 日是最优解、最短解。