Rectangles

$\mathcal{O}(n^2)$ 做法（嘲讽 Sam $\mathcal{O}(n^2\log n)$）。

HDU 2013。

给定 $n,m,k$ 以及 $k$ 个关键点 $(X_i,Y_i)$。求有多少个 $1\le x_1\le x_2\le n,1\le y_1\le y_2\le m$，满足矩形 $(x_1,y_1)(x_2,y_2)$ 内部至少有一个关键点。

$1\le n,m\le 10^9,1\le k\le 1000$。

首先我们有一个错误的做法：

对于每一个关键点 $(X_i,Y_i)$，计算所有包含这个点的矩形个数，即 $X_iY_i(n-X_i+1)(m-Y_i+1)$ 个矩形。

然后将所有关键点的答案累加。

错误的原因是，一个矩形可能包含多个点，会被重复计算很多次。

于是为了保证不算重，我们在计算关键点 $(X_i,Y_i)$ 时，不妨钦定关键点 $i$ 为包含其的矩形中编号最大的。这样每一个矩形就只会在其编号最大的点处被计算。

为了方便，我们将所有关键点按 $X_i$ 为第一关键字，$Y_i$ 为第二关键字排序并去重。

那么枚举 $i$，计算时我就需要计算所有不包含编号 $>i$ 的矩形个数。

接下来有一个错误但是具有启发性的做法：

由于所有不能被矩形包含的关键点都在 $i$ 的右边或者上面，于是我们得出结论：$(x_1,y_1)$ 可以在 $1\sim X_i$ 和 $1\sim Y_i$ 内随便取（注意这里有问题）。

于是被限制的就只有 $(x_2,y_2)$ 了。

然后我们又发现，一个编号 $j(j>i)$ 的关键点被包含。当且仅当 $x_2\ge X_j,y_2\ge Y_j$，这可以看成是一个矩形覆盖，所有被覆盖的点都不能被选择。

那么我们可以使用单调栈处理这些点的面积并，然后拿总面积减去即可。

然而上面的实际上有问题：对于那些编号 $j(j>i)$ 的且 $Y_j<Y_i$ 的点，这些点实际上会影响 $(x_1,y_1)$！（自己画图）。

具体的，不妨设 $x_2,y_2$ 已经确定，那么对于那些 $j>i$ 的 $j$ 且 $Y_j<Y_i$，那么如果满足 $Y_j\ge y_1$，那么这个矩形就会包含 $j$！于是，尽管 $x_1$ 没有限制，但是 $y_1$ 必须 $\ge\max\limits_{Y_j<Y_i\land j>i}\{Y_j\}$。

那么在上面处理 $x_2,y_2$ 的单调栈的过程中，我们需要同步维护一个指针 $p$ 维护所有 $Y_j<Y_i$ 的 $j$，以及 $p$ 以前的最大值 $M$。那么如果上面单调栈得到的 $(x_2,y_2)$ 的方案数为 $S$，那么总答案就会累加 $SX_i(Y_i-M)$。

这样你就得到了暴打 $\mathcal{O}(n^2\log n)$ 的 $\mathcal{O}(n^2)$ 做法。