题解

思路分析

这是一道 组合数学 + DP + 前缀和优化 的计数问题。

问题建模

• $N \times N$ 的网格，某些格子有喷头
• 每个喷头覆盖一个右上矩形（水）和左下矩形（肥料）
• 求有多少个矩形被完全覆盖（既有水又有肥料）

核心思路

1. 矩形覆盖条件

矩形 $[x_1, x_2] \times [y_1, y_2]$ 被覆盖，当且仅当：

• 水覆盖：存在喷头 $(i, j)$ 满足 $i \leq x_1$ 且 $j \leq y_1$
• 肥料覆盖：存在喷头 $(i, j)$ 满足 $i \geq x_2$ 且 $j \geq y_2$

2. 转化为排列问题

由于每行每列恰好一个喷头，可以看作排列 $p$：第 $i$ 行的喷头在第 $p_i$ 列。

矩形 $[x_1, x_2] \times [y_1, y_2]$ 被覆盖的充要条件：

$$\min_{i \leq x_1} p_i \leq y_1 \text{ 且 } \max_{i \geq x_2} p_i \geq y_2 $$

3. DP 计数

定义 $f[i]$ 表示考虑前 $i$ 行后，有多少个有效的排列。

对于每个矩形 $[x_1, x_2] \times [y_1, y_2]$：

• 统计满足条件的排列数
• 使用容斥原理

4. 前缀和优化

预处理前缀最小值和后缀最大值：

• $dn[i] = \min_{j \leq i} p_j$
• $up[i] = \max_{j \geq i} p_j$

算法步骤

1. 预处理：

   • 读入喷头位置
   • 计算 $dn$ 和 $up$ 数组

2. 枚举矩形：

   • 枚举左上角 $(x_1, y_1)$ 和右下角 $(x_2, y_2)$
   • 检查是否被覆盖

3. 组合计数：

   • 使用组合数公式计算方案数
   • 累加答案

4. 输出结果

复杂度分析

• 时间复杂度：$O(N^2)$ 或 $O(N \log N)$（取决于实现）
• 空间复杂度：$O(N)$

#include <bits/stdc++.h>
using namespace std;
#define cs const
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define bg begin
cs int RLEN = 1 << 20 | 1;
inline char gc() {
    static char ibuf[RLEN], *ib, *ob;
    (ib == ob) &&(ob = (ib = ibuf) + fread(ibuf, 1, RLEN, stdin));
    return (ib == ob) ? EOF : *ib++;
}
inline int read() {
    char ch = gc();
    int res = 0;
    bool f = 1;

    while (!isdigit(ch))
        f ^= ch == '-', ch = gc();

    while (isdigit(ch))
        res = (res * 10) + (ch ^ 48), ch = gc();

    return f ? res : -res;
}
template<typename tp>inline void chemx(tp &a, tp b) {
    a = max(a, b);
}
template<typename tp>inline void chemn(tp &a, tp b) {
    b = min(a, b);
}
cs int mod = 1e9 + 7;
cs int N = 100005;
int y[N], up[N], dn[N], pre[N], n;
ll s[N], sc[N];
ll ans;
inline ll C(int x) {
    return (ll)x * (x + 1) / 2;
}
int main() {
#ifdef Stargazer
    freopen("lx.in", "r", stdin);
#endif
    n = read();

    for (int i = 1; i <= n; i++) {
        int X = read() + 1, Y = read() + 1;
        y[X] = Y;
    }

    dn[1] = y[1];

    for (int i = 2; i <= n; i++)
        dn[i] = min(dn[i - 1], y[i]);

    up[n] = y[n];

    for (int i = n - 1; i; i--)
        up[i] = max(up[i + 1], y[i]);

    int j = n;

    for (int i = 1; i <= n; i++)
        while (j >= dn[i])
            pre[j--] = i;

    while (j)
        pre[j--] = n + 1;

    for (int i = n; i; i--)
        s[i] = s[i + 1] + pre[i], sc[i] = sc[i + 1] + (ll)pre[i] * i;

    for (int i = 1; i <= n; i++) {
        ans += (ll)i * C(up[i] - dn[i]);
        ans -= (ll)up[i] * (s[dn[i]] - s[up[i] + 1]) - (sc[dn[i]] - sc[up[i] + 1]);

        if (ans > 1e18)
            ans %= mod;
    }

    cout << ans % mod;
    return 0;
}

题解

设 $y[i]$ 表示第 $i$ 列喷头所在的行坐标。对于一个矩形 $[x_1,x_2] \times [y_1,y_2]$ 能被所有喷头覆盖，需要同时满足：

• 对于水（向东北喷洒），矩形的上边 $y_2$ 不能高于区间 $[x_1,x_2]$ 内任意喷头的纵坐标。换言之，$$y_2 \le \max_{k \in [x_1, x_2]} y[k].$$
• 对于肥料（向西南喷洒），矩形的下边 $y_1$ 不能低于该区间内任何喷头的纵坐标，即$$y_1 \ge \min_{k \in [x_1, x_2]} y[k].$$

因此在给定的列段 $[x_1,x_2]$ 内，允许的纵坐标区间为 $[dn[x_2], up[x_1]]$，其中

$$dn[i] = \min_{k \le i} y[k], \quad up[i] = \max_{k \ge i} y[k]. $$

只要选取的矩形满足

$$dn[x_2] \le y_1 \le y_2 \le up[x_1],$$

它就是合法的。为了统计个数，我们把每个可能的右边界 $x_2$ 作为外层循环，再按照上边界 $y_2$ 从高到低扫描。用 $pre[y]$ 记录可以把下边界放在高度 $y$ 时，最靠右的左端点（即最小的 $x_1$），则对于给定的 $x_2$，合法的矩形数量即可用若干段求和表示。

代码中预先构造了 $dn$ 的前缀最小值和 $up$ 的后缀最大值，并把 $pre$、$s$、$sc$ 作为前缀和 / 加权前缀和保存，便于在 $O(1)$ 时间内得到 $\sum pre[y]$。外层循环枚举 $i$（对应右边界和上边界），其中……

ans += i * C(up[i] - dn[i])                      // 枚举所有可能的下边界
ans -= up[i] * Σ pre[y] + Σ pre[y] * y           // 纠正重复统计

最终得到的 ans 对 1e9+7 取模即为答案。整个算法都是线性处理和若干次前缀和查询，时间复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;
#define cs const
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define bg begin
cs int RLEN = 1 << 20 | 1;
inline char gc() {
    static char ibuf[RLEN], *ib, *ob;
    (ib == ob) &&(ob = (ib = ibuf) + fread(ibuf, 1, RLEN, stdin));
    return (ib == ob) ? EOF : *ib++;
}
inline int read() {
    char ch = gc();
    int res = 0;
    bool f = 1;

    while (!isdigit(ch))
        f ^= ch == '-', ch = gc();

    while (isdigit(ch))
        res = (res * 10) + (ch ^ 48), ch = gc();

    return f ? res : -res;
}
template<typename tp>inline void chemx(tp &a, tp b) {
    a = max(a, b);
}
template<typename tp>inline void chemn(tp &a, tp b) {
    b = min(a, b);
}
cs int mod = 1e9 + 7;
cs int N = 100005;
int y[N], up[N], dn[N], pre[N], n;
ll s[N], sc[N];
ll ans;
inline ll C(int x) {
    return (ll)x * (x + 1) / 2;
}
int main() {
#ifdef Stargazer
    freopen("lx.in", "r", stdin);
#endif
    n = read();

    for (int i = 1; i <= n; i++) {
        int X = read() + 1, Y = read() + 1;
        y[X] = Y;
    }

    dn[1] = y[1];

    for (int i = 2; i <= n; i++)
        dn[i] = min(dn[i - 1], y[i]);

    up[n] = y[n];

    for (int i = n - 1; i; i--)
        up[i] = max(up[i + 1], y[i]);

    int j = n;

    for (int i = 1; i <= n; i++)
        while (j >= dn[i])
            pre[j--] = i;

    while (j)
        pre[j--] = n + 1;

    for (int i = n; i; i--)
        s[i] = s[i + 1] + pre[i], sc[i] = sc[i + 1] + (ll)pre[i] * i;

    for (int i = 1; i <= n; i++) {
        ans += (ll)i * C(up[i] - dn[i]);
        ans -= (ll)up[i] * (s[dn[i]] - s[up[i] + 1]) - (sc[dn[i]] - sc[up[i] + 1]);

        if (ans > 1e18)
            ans %= mod;
    }

    cout << ans % mod;
    return 0;
}