CF627E Orchestra 题解
Visits: 266
题意
- 在一个 $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;
}