【题解】AT2394 [ARC071B] 井井井 / ###

· · 题解

\rm{Description}

在平面直角坐标系中，给定 n 条平行于 y 轴的线和 m 条平行于 x 轴的线，求由这些线组成的矩形的面积和。

\rm{Solution}

\rm{subtask} \rm{1}

考虑暴力做法，枚举矩形的左上角和右下角，也就是求：

\sum_{1\leq i\leq j\leq n}\sum_{1\leq k\leq l\leq m}(x_j-x_i)\cdot(y_l-y_k)

时间复杂度是 \mathcal{O}(n^2m^2) .

\rm{subtask} \rm{2}

对于任意一个矩形，想要确定它，只需要固定一条平行于 x 轴的线段和一条平行于 y 轴的线段。

所以最终的答案可以写成：

\sum_{i\leq i\leq j\leq n}(x_j-x_i)\sum_{1\leq k\leq l\leq m}(y_l-y_k)

记 A=\sum\limits_{1\leq i\leq j\leq n}(x_j-x_i)，B=\sum\limits_{1\leq k\leq l\leq m}(y_l-y_k)，那么我们可以分开计算 A 和 B。也就是分别计算：所有平行于 x 轴的线段长度和，以及所有平行于 y 轴的线段长度和。

这样可以得到 \mathcal{O}(n^2) 级别的算法。

\rm{subtask} \rm{3}

思路：

对于满分做法，我们期望 \mathcal{O}(n) 的算法，现在想要进一步简化上面的式子。

考虑如何快速求出所有平行于 x 轴的线段长度和。容易想到，我们只需要统计每条小线段被算了几次。显然对于线段 (x_{i-1}, x_{i})，被计算了 (i - 1) \times(n-i-1) 次，于是我们就有了线性的做法。

对于平行于 y 轴的线段，计算方法完全相同。

如果到此为止您看懂了，那可以直接看代码了，如果没看懂，请看下面这部分。

具体地：

定义一个线段是基本线段，当且仅当线段的两个端点之间不存在另一个端点，那么我们可以将每条线段拆成基本线段的和的形式，之后分别计算每条基本线段的贡献。

比如：

对于这张图，线段长度和为 |AB|+|AC|+|AD|+|BC|+|BD|+|CD|.

那么我们将上图中每个线段表示成基本线段的和的形式，比如 |AC|=|AB|+|BC|，整理之后即：

3|AB|+4|BC|+3|CD|

现在考虑如何计算每条基本线段的贡献。

根据小学数学知识，线段 (x_i, x_{i - 1}) 被算的次数是 (i-1)\times (n - i - 1) ，这样我们就能 \mathcal{O}(n) 地算出平行于 x 轴的线段长度和。

对于平行于 y 轴的，用同样的方法计算。

\rm{Code}

#include <bits/stdc++.h>
#define int long long
#define MAXN 100008
using namespace std;
int n, m, x[MAXN], y[MAXN];
int A, B; //A为所有平行于 x 轴的线段长度和，B为平行于 y 轴的线段长度和
const int mod = 1e9 + 7;
signed main() {
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lld", &x[i]);
    for(int i = 1; i <= m; i++) scanf("%lld", &y[i]);
    sort(x + 1, x + n + 1); //横纵坐标升序排序
    sort(y + 1, y + m + 1);
    for(int i = 2; i <= n; i++) { //计算与x轴平行的所有线段的长度和
        A = (A + (x[i] - x[i - 1]) * (i - 1) * (n - i + 1)) % mod;
    }
    for(int i = 2; i <= m; i++) {
        B = (B + (y[i] - y[i - 1]) * (i - 1) * (m - i + 1)) % mod;
    }
    printf("%lld\n", A * B % mod);
    return 0;
}