CF627E Orchestra 题解

作者: xht37 分类: 题解 发布时间: 2020-03-05 13:45

Visits: 220

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注