【AtCoder-2394】井井井

更好的阅读体验：TonyYin - Blog ↗ 题目地址：AT2394 [ARC071B] 井井井 / ### – 洛谷 | 计算机科学教育新生态 ↗

$\rm{Description}$#

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

$\rm{Solution}$#

$\rm{subtask}$ $\rm{1}$#

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

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

$\rm{subtask}$ $\rm{2}$#

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

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

记 $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|$，整理之后即：

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

根据小学数学知识，线段 $(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;
}