20231008题解

发表于 2023-10-08 分类于信奥，题解阅读次数： 19

T3

什么样的矩形可能是某个点集的最小覆盖矩形？

一定是四条边都经过了至少一个关键点的矩形。

换句话说，我们可以通过枚举能够通过关键点的水平线和竖直线来枚举矩形数量。

一个自然的想法是，枚举左右两条竖直线，统计有多少条水平线满足要求。

要求是什么要求呢？

他们本身至少经过被夹在两根竖直线之间的一个关键点。
他们在竖直线上截出的一条线段至少要经过一个关键点。

怎么做呢？我们用一个双指针枚举两条水平线的界。保证双指针之间至少在竖直线上截出一个点，则我们统计下面的水平线比双指针下端低，上面的水平线比双指针上端高的个数。但这样仍然会重复，所以我们把上一次双指针的下端记录下来，则下面的水平线的范围就是“上一次下端指针到这一次下端指针”，这样就不重不漏了。

最后看一下怎么计算。如果双指针上端以上有一些水平线 $y_{1}, y_{2}, . . ., y_{p}$ ，而下端以下有一些水平线 $y_{p + 1}, y_{p + 2}, . . ., y_{q}$ ，两条竖直线差距是 $L$ ，则总面积就是 $\sum_{i = 1}^{p} \sum_{j = p + 1}^{q} (y_{i} - y_{j}) = [(q - p) \sum_{i} y_{i}] - (p \sum_{j} y_{j})$ 。所以，我们要维护被两条竖直线夹起来的点中，大于/小于某个值的 $y$ 值和以及大于/小于某个值的 $y$ 的个数，这用两棵值域树状数组即可。

#include <bits/stdc++.h>
using namespace std;

template<class T>
void read(T &r) {
    r = 0; char ch; bool f = false;
    while (!isdigit(ch = getchar())) if (ch == '-') f ^= 1;
    while (isdigit(ch)) r = r * 10 + ch - 48, ch = getchar();
    if (f) r = -r;
}

const int maxn = 1e4 + 5, maxv = 2.5e3 + 5;
const long long mod = 1e9 + 7;
vector<int> y_in_x[maxv], tmp;
int n, c[maxv], d[maxv];
long long ans;
bool by[maxv], ii[maxv], ij[maxv];

void update(int c[], int pos, int w) { for (; pos <= 2500; pos += (pos & -pos)) c[pos] += w; }
int ask(int c[], int pos) { int res = 0; for (; pos; pos -= (pos & -pos)) res += c[pos]; return res; }
int ask(int c[], int l, int r) { return l > r ? 0LL : (ask(c, r) - ask(c, l - 1)); }

int main() {
    // freopen("rectangle.in", "r", stdin), freopen("rectangle.out", "w", stdout);
    read(n);
    for (int i = 1, x, y; i <= n; i++) read(x), read(y), y_in_x[x].emplace_back(y);
    for (int i = 1; i <= 2500; i++) sort(y_in_x[i].begin(), y_in_x[i].end());
    for (int i = 1; i <= 2500; i++) if (!y_in_x[i].empty()) {
        memset(by, 0, sizeof by), memset(c, 0, sizeof c), memset(d, 0, sizeof d);
        memset(ii, 0, sizeof ii); memset(ij, 0, sizeof ij);
        for (int y : y_in_x[i]) ii[y] = true, by[y] = true, update(c, y, y), update(d, y, 1);
        for (int j = i + 1; j <= 2500; j++) {
            if (!y_in_x[j].empty()) {
                tmp = y_in_x[i];
                for (int y : y_in_x[j]) {
                    ij[y] = true;
                    if (!by[y]) by[y] = true, update(c, y, y), update(d, y, 1);
                    if (!ii[y]) tmp.emplace_back(y);
                }
                sort(tmp.begin(), tmp.end());
                int l = 0, ci = 0, cj = 0, pre = 0;
                for (int r = 0; r < tmp.size(); r++) {
                    ci += ii[tmp[r]], cj += ij[tmp[r]];
                    if (!ci || !cj) continue;
                    while ((ci - ii[tmp[l]]) && (cj - ij[tmp[l]])) ci -= ii[tmp[l]], cj -= ij[tmp[l]], l++;
                    (ans += (1LL * ask(c, tmp[r], 2500) * ask(d, pre + 1, tmp[l]) - 1LL * ask(d, tmp[r], 2500) * ask(c, pre + 1, tmp[l])) % mod * (j - i)) %= mod;
                    pre = tmp[l];
                }
                for (int y : y_in_x[j]) ij[y] = false;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

T4

一个回字形只需要由两个点确定：左上角和右下角。我们考虑枚举右下角，然后计算符合条件的左上角。

首先确定一点：左上角与右下角一定在同一根对角线上，这启示我们可以按照对角线枚举。

如果右下角是 $(i, j)$ ，则与右下角相邻的两条边会各有一个最长的不碰到禁止点的长度，我们把两边的最小值记作 $g_{i, j}$ 。同样的，如果左上角是 $(x, y)$ ，我们把两边限制的最小值记作 $f_{x, y}$ 。

那么，考虑到题目的限制，只有这样的 $(x, y)$ 能与 $(i, j)$ 配对：

${\begin{cases} i - x = j - y \\ L \leq i - x + 1 \leq f_{i, j} \\ i - x + 1 \leq g_{x, y} \end{cases}$

考虑到 $(i, j)$ 是枚举的，则整理得：

${\begin{cases} i - j = x - y \\ i - f_{i, j} + 1 \leq x \leq i - L + 1 \\ x + g_{x, y} > i \end{cases}$

注意到第三条左边是确定的，而第二条是一个区间，所以我们可以分别求 $x \leq i - L + 1$ 的个数和 $x \leq i - f_{i, j}$ 的个数再相减。对于只剩下两个不等限制的子问题，很容易看出这是一个二维偏序。

所以我们枚举整个对角线，先枚一边记录下所有的询问要求的 $x$ 小于等于的值以及 $x + g_{x, y}$ 大于的值，然后再枚举一遍，将 $x + g_{x, y}$ 依次放入值域树状数组中，并对 $x$ 小于等于的值等于当前值的询问进行查询，即查询 $x + g_{x, y}$ 符合条件的点的个数，最后再将离线查询的结果整合到答案里。

#include <bits/stdc++.h>
using namespace std;

template<class T>
void read(T &r) {
    r = 0; char ch; bool f = false;
    while (!isdigit(ch = getchar())) if (ch == '-') f ^= 1;
    while (isdigit(ch)) r = r * 10 + ch - 48, ch = getchar();
    if (f) r = -r;
}

struct node { int b, val; node(int b, int val): b(b), val(val) {} };
const int maxn = 3e3 + 5;
int n, m, l, p, f[maxn][maxn], g[maxn][maxn], h[maxn][maxn], c[maxn];
long long ans;
vector<node> q[maxn << 1];
bool mp[maxn][maxn];

void update(int pos, int w) { for (; pos <= 3e3; pos += (pos & -pos)) c[pos] += w; }
int ask(int pos) { int res = 0; for (; pos; pos -= (pos & -pos)) res += c[pos]; return res; }

int main() {
    // freopen("rampart" ".out", "w", stdout);
    read(n); read(m); read(l); read(p);
    for (int i = 1, x, y; i <= p; i++) read(x), read(y), mp[x][y] = true;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) g[i][j] = (mp[i][j] ? 0 : g[i][j - 1] + 1), h[i][j] = (mp[i][j] ? 0 : h[i - 1][j] + 1);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) g[i][j] = min(g[i][j], h[i][j]);
    for (int i = n; i >= 1; i--) for (int j = m; j >= 1; j--) f[i][j] = (mp[i][j] ? 0 : f[i][j + 1] + 1), h[i][j] = (mp[i][j] ? 0 : h[i + 1][j] + 1);
    for (int i = n; i >= 1; i--) for (int j = m; j >= 1; j--) f[i][j] = min(f[i][j], h[i][j]);
    for (int s = n - 1; s >= 1 - m; s--) {
        memset(c, 0, sizeof c);
        for (int i = 0; i <= n + m; i++) q[i].clear();
        for (int i = max(s, 0) + 1; i <= min(n, m + s); i++) {
            int j = i - s, id = i - max(s, 0);
            if (i < l || j < l) continue;
            if (g[i][j] >= l) q[id - g[i][j]].emplace_back(-1, j), q[id - l + 1].emplace_back(1, j);
        }
        for (int i = max(s, 0) + 1; i <= min(n, m + s); i++) {
            int j = i - s, id = i - max(s, 0);
            if (f[i][j] >= l) update(f[i][j] + j - 1, 1);
            for (auto &x : q[id]) ans += x.b * (ask(3e3) - ask(x.val - 1));
        }
    }
    printf("%lld\n", ans);
    return 0;
}