2020-2021:teams:farmer_john:2sozx:cf_1396d_rainbow_rectangles
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2sozx:cf_1396d_rainbow_rectangles [2020/09/04 11:08] 2sozx 创建 |
2020-2021:teams:farmer_john:2sozx:cf_1396d_rainbow_rectangles [2020/09/04 11:27] (当前版本) 2sozx [题解] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| =====题意===== | =====题意===== | ||
| $L \times L$ 的网格平面，其中有 $n$ 的点，每个点在网格的中心。每个点有一个颜色，总共有 $k$ 个颜色，现在求多少个矩形包含了所有 $k$ 种颜色。$n,k \le 2000, L \le 10^9$ | $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))$ 。 | ||
2020-2021/teams/farmer_john/2sozx/cf_1396d_rainbow_rectangles.1599188880.txt.gz · 最后更改: 2020/09/04 11:08 由 2sozx
