主要思路

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

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

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

详细见代码：

Continue reading →

区间除和开方要解决的就是以下两种操作：

1. \(\forall i \in [l, r], \lfloor \frac{a_i}{d} \rfloor \to a_i\)
2. \(\forall i \in [l, r], \lfloor \sqrt{a_i} \rfloor \to a_i\)

正常的标记操作是很难实现这些操作的，然而我们可以把这些操作进行一些转换，因为这些操作在一定的值域范围内是可以批量处理的。换句话说，如果区间内极差小，那么除法或开方的效果在区间内等效，所以可以转化成减法来进行实现。

拿除法举例：在区间\((l, r)\)中，如果\( \max(S) – \lfloor \frac{\max(S)}{d} \rfloor = \min(S) – \lfloor \frac{\min(S)}{d} \rfloor \)，那么我们就可以把这个差值作为减数，用正常的加减方式进行标记。

Continue reading →