题解

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