CVBB ACM Team

$L \times L$ 的网格平面，其中有 $n$ 的点，每个点在网格的中心。每个点有一个颜色，总共有 $k$ 个颜色，现在求多少个矩形包含了所有 $k$ 种颜色。$n,k \le 2000, L \le 10^9$

首先我们可以枚举矩形的左边和右边所在的 $x$，先固定矩形的左侧边缘 $x_l$，向右侧扫。对于每个点记录 $pre_i$ 为在区间内颜色相同，$y$ 值小于等于自己的点的 $y$ 值；$nxt_i$ 为在区间内颜色相同，$y$ 值大于等于自己的点的 $y$ 值。

考虑先将 $x_l \sim L$ 内部所有点都考虑到。令 $f(i)$ 表示纵坐标为 $i$ 要满足包含 $k$ 个颜色的最低 $y$ 值，显然随着 $i$ 的下降 $f_i$ 是单调不增的，这为下面的操作提供了复杂度的保证。考虑左右侧确定时的答案是多少，$ans = \sum_{i = 0}^{L} (L + 1 - f_i)$，可以用线段树维护 $f_i$ 的和。

现在考虑删除矩形右侧的一列，对于一个点 $i$ 被删除，那么 $pre_i + 1 \sim y_i$ 的点的 $f$ 值显然要和 $nxt_i$ 取最大值，这个也可以用线段树维护，由于 $f_i$ 的单调性，线段树的复杂度是正确的，每次删除后统计答案即可，复杂度 $O(n^2\log(n))$ 。