CF1396D Solution
题面:
给你一个 \(L\times L\) 的矩形,有 \(n\) 个点放在不同的格子内,每个点有颜色,共 \(k\) 种颜色,求有多少个矩形满足其内部含有所有颜色的点,对 \(10^9+7\) 取模。
\(k\le n\le2000,L\le10^9\)。
首先离散化。
看到数据范围说明可以枚举矩形的某个端点或者上下(左右)边界。枚举端点没什么用,考虑枚举上下边界 \(u,d\)。
现在只看第 \(u\) 行到第 \(d\) 行,我们要统计有多少对 \((l,r)\) 满足第 \(l\) 列到第 \(r\) 列是满足条件的。
这是一个典型问题。设 \(f_i\) 表示最小的 \(j\) 满足第 \(i\) 列到第 \(j\) 列是满足条件的,那么 \(l=i\) 的贡献即为 \(L-f_i+1\)。
设 \(m\) 为 \([u,d]\) 内点数,\(c_i\) 表示离散化后的点的列编号,答案即为
\[\begin{aligned} \sum_{i=1}^m(c_i-c_{i-1})(L-f_i+1)&=\sum_{i=1}^m(c_i-c_{i-1})(L+1)-\sum_{i=1}^m(c_i-c_{i-1})f_i\\ &=c_m(L+1)-\sum_{i=1}^m(c_i-c_{i-1})f_i \end{aligned}\]至于如何求 \(f\),考虑设 \(nxt_i\) 为第 \(i\) 列所有颜色的下一个出现的列的最大值。
如果现在求出了 \(f_i\),显然 \(f_{i+1}=\max(f_i,nxt_i)\)。每次处理 \(f\) 是 \(\mathcal O(n)\) 的,我们得到了一个 \(\mathcal O(n^3)\) 的算法。
现在考虑固定 \(u\),在枚举 \(d\) 时优化。你发现如果从小到大枚举 \(d\) 会出现插入点的操作,这使得有些 \(nxt\) 需要缩小,不方便处理 \(\max\)。
于是考虑反过来,从大到小枚举 \(d\),把插入变成删除,这样子 \(nxt\) 只会增大。
\(f\) 数组实质上是 \(nxt\) 数组的前缀最大值,那么我们修改 \(nxt\) 时只需要将其后面的某一段 \(f\) 统一赋值即可。这个赋值的边界可以二分得到。
那么你现在需要支持 \(f\) 数组的:区间赋值,总体求和。这个显然可以线段树维护。
这样每个 \(u\) 耗费 \(\mathcal O(n\log n)\) 的时间,总复杂度即为 \(\mathcal O(n^2\log n)\)。
标签:nxt,sum,solution,枚举,cf1396d,mathcal,矩形,赋值 From: https://www.cnblogs.com/iorit/p/18040099