CF627E Orchestra 题解

CF627E Orchestra

题意

• 在一个 $r \times c$ 的矩阵中有 $n$ 个点，问有多少个连续子矩阵至少包含 $k$ 个点。
• $r,c,n \le 3 \times 10^3$，$k \le 10$。

题解

这题不同复杂度的做法非常多。

$\mathcal O(r^3c^3 + n)$

最朴素的做法，枚举连续子矩阵的上下左右边界，暴力计算其中的点数。

也就是 https://www.luogu.com.cn/problem/CF635A 这题。

$\mathcal O(r^2c^2 + n)$

对于 $\mathcal O(r^3c^3)$ 做法的优化，计算连续子矩阵中的点数时，前缀和优化一下。

$\mathcal O(r^2c + n)$

只枚举上下边界，中间 two pointers 扫一遍。

$\mathcal O(r^2 + rc + rnk)$

注意到 $n,k$ 都非常小，其中 $n,r,c$ 同阶，而 $k$ 只有 $10$。

考虑枚举上边界 $i$，下边界从 $i$ 往下推，用链表按列为第一关键字，行为第二关键字的顺序维护所有点以及点之后第 $k-1$ 个点的列。

往下推的过程，相当于往链表里动态加点的过程，注意到每次加点只会改变其前面 $k-1$ 个点的信息，那么暴力更新即可。

但是链表无法随机访问，无法实现动态加点。那么换个方向，从 $r$ 往上推到 $i$，动态加点改为动态删点，就可以用链表维护了。

代码

const int N = 3e3 + 7;
int r, c, n, k, p[N], q[N], t[N], v[N];
pi a[N];
vector<pi> R[N], C[N];
ll ans;

inline ll calc(int i, int j, int o) {
	ll ret = 1ll * (t[o] - j + 1) * (a[o].se - a[p[o]].se) * (c - a[v[o]].se + 1);
	return t[o] = j - 1, ret;
}

int main() {
	rd(r), rd(c), rd(n), rd(k);
	for (int i = 1, x, y; i <= n; i++)
		rd(x), rd(y), a[i] = mp(x, y), R[x].pb(mp(y, i)), C[y].pb(mp(x, i));
	for (int i = 1; i <= r; i++) sort(R[i].begin(), R[i].end());
	for (int i = 1; i <= c; i++) sort(C[i].begin(), C[i].end());
	a[n+1] = mp(r + 1, c + 1);
	for (int i = 1; i <= r; i++) {
		int o = 0;
		for (int j = 1; j <= c; j++)
			for (pi x : C[j])
				if (x.fi >= i)
					q[o] = x.se, p[x.se] = o, o = x.se, t[o] = r, v[o] = 0;
		q[o] = q[n+1] = v[n+1] = n + 1, t[n+1] = r, o = 0;
		for (int j = 1; j <= k; j++) o = q[o];
		for (int j = q[0]; j != n + 1; j = q[j], o = q[o]) v[j] = o;
		for (int j = r; j >= i; j--)
			for (pi x : R[j]) {
				ans += calc(i, j, q[x.se]), o = x.se;
				for (int l = 1; o && l <= k; l++, o = p[o]) ans += calc(i, j, o);
				q[p[x.se]] = q[x.se], p[q[x.se]] = p[x.se];
				int w = o = q[o];
				for (int l = 1; l < k; l++) w = q[w];
				while (o != q[x.se]) v[o] = w, o = q[o], w = q[w];
			}
	}
	print(ans);
	return 0;
}