题目描述

难度分:$1641$

输入$n$，$m(2 \leq n,m \leq 2 \times 10^5)$，长为$n$的严格递增数组$x(-10^9 \leq x[i] \leq 10^9)$，长为$m$的严格递增数组$y(-10^9 \leq y[i] \leq 10^9)$。

从$x$中选两个数$x[i_1]$、$x[i_2]$，组成直线$X=x[i_1]$，$X=x[i_2]$，其中$i_1 \lt i_2$。

从$y$中选两个数$y[j_1]$、$y[j_2]$，组成直线$Y=y[j_1]$，$Y=y[j_2]$，其中$j_1 \lt j_2$。

这四条直线包围的区域是一个矩形，计算所有矩形的面积之和。由于答案可能非常大，将结果模上$10^9+7$输出。

输入样例$1$

3 3
1 3 4
1 3 6

输出样例$1$

60

输入样例$2$

6 5
-790013317 -192321079 95834122 418379342 586260100 802780784
-253230108 193944314 363756450 712662868 735867677

输出样例$2$

835067060

算法

贡献法+动态规划

先将两个坐标数组$x$、$y$转化一下，转成两个数组$dx$、$dy$，$dx[i]$表示的是$x[i]$到$x[i+1]$的距离，也就是数轴上这个线段的长度，$dy[i]$的含义同理，数组$dx$和数组$dy$的长度分别为$n-1$和$m-1$。

接下来考虑$x$方向的边长对答案的贡献，对于$x$方向，我们要找出所有矩形在此方向上的边长之和$sx$，用动态规划来求解。

状态定义

$fx[i]$表示以线段$dx[i]$结尾的所有边长总和。

状态转移

如果新加入边$dx[i]$，首先它可以接在$fx[i-1]$包括的所有边的后面，同时还可以只用自己一条线段构成边，因此一共有$[1,i]$，$[2,i]$，……，$[i,i]$一共$i$种边长，状态转移方程为

$fx[i]=fx[i-1]+i \times dx[i]$

所有矩形在$x$轴方向上的贡献就是$sx=\Sigma_{i=1}^{n-1}fx[i]$。

然后就可以枚举所有$y$方向上的边长，用这些边长乘以$sx$再累加起来就是答案。但$m$的范围也是很大的，直接枚举肯定会超时。此时发现所有$y$方向上的边长乘的都是$sx$，这也就意味着公因子是可以提出来的，即$x$轴方向和$y$方向是相互独立的，可以分别考虑。

用同样的方式计算出所有矩形在$y$方向上的贡献$sy$，最后的答案就是$sx \times sy$。

复杂度分析

时间复杂度

计算$dx$和$dy$只需要分别遍历$x$和$y$两个数组，动态规划都是线性DP，因此算法的时间复杂度为$O(n+m)$。

空间复杂度

开辟的$dx$和$dy$数组，以及两个DP数组都和衍生出它们的原数组$x$和$y$同一规模，因此额外空间复杂度为$O(n+m)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 100010, MOD = 1e9 + 7;
int n, m;
int x[N], y[N], dx[N], dy[N];
int dpx[N], dpy[N];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &x[i]);
        if(i >= 2) {
            dx[i - 1] = x[i] - x[i - 1];
        }
    }
    for(int i = 1; i <= m; i++) {
        scanf("%d", &y[i]);
        if(i >= 2) {
            dy[i - 1] = y[i] - y[i - 1];
        }
    }
    memset(dpx, 0, sizeof dpx);
    int sx = 0;
    for(int i = 1; i < n; i++) {
        dpx[i] = (dpx[i - 1] + (LL)i*dx[i]%MOD)%MOD;
        sx = (sx + dpx[i])%MOD;
    }
    memset(dpy, 0, sizeof dpy);
    int sy = 0;
    for(int i = 1; i < m; i++) {
        dpy[i] = (dpy[i - 1] + (LL)i*dy[i]%MOD)%MOD;
        sy = (sy + dpy[i])%MOD;
    }
    printf("%d\n", (LL)sx*sy%MOD);
    return 0;
}