主要思路

\(\Theta(n^2)\)暴力还是很好写的，先枚举水平线，然后再分上下讨论；讨论中，我们都要从左往右枚举，但是我们有两个指针\(lptr, rptr\)，我们可以在过程中维护在\([lptr, rptr]\)之间的颜色数始终严格小于\(k\)，然后再用点个数更新答案。

那么正解就没这么好写了。我们考虑在\(k\)中枚举一个被排除的颜色，然后分情况讨论：

• 按\(x\)排序，相邻点对做垂直线，两线之间的点个数可能成为答案。
• 向上看，我们可以把点按\(y\)降序排序，然后让矩形的横线段\([l, r]\)强行\(\in x_i\)，也就是置横线段为当前点之上。用 multiset 查询当前点前驱后继的\(x\)作为矩形的横线范围，然后把当前点的\(y + 1\)作为基准线，用主席树查询当前矩形内的点数。
• 向下看类似。

详细见代码：

Continue reading →