ARC 071 D - 井井井 ( Math )

D: 井井井 / ### - AtCoder Regular Contest 071 | AtCoder

題意：
在二維座標系上，給 N 個縱線，M 個橫線，問所有可形成的四邊形面積總和。輸出答案對 1e9 + 7 取模。

制約：
2≤n,m≤1e5
xi,yi は整数である。

解法：
首先顯然兩個維度可以獨立看待，因此考慮一維的計算。可以知道，在一維問題上要計算的其實是所有點對的距離總和。將它們排序後，用遞推的方式更新答案即可。一個新的線 i 的貢獻是上一個線 i - 1 的貢獻 + 前面的線的數量 * ( A[ i ] - A[ i - 1 ] )。

時間 / 空間複雜度：
O( N lg N ) / O( N )

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = ( int ) 1e9 + 7;
 
const int MAXN = ( int ) 1e5;
const int MAXM = ( int ) 1e5;
 
int N, M;
int X[ MAXN ], Y[ MAXM ];
 
signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < N; ++i ){
    cin >> X[ i ];
  }
  for( int i = 0; i < M; ++i ){
    cin >> Y[ i ];
  }
  sort( X, X + N );
  sort( Y, Y + M );
  int a = 0, b = 0;
  for( int i = 1, prev = 0; i < N; ++i ){
    ( a += prev ) %= MOD;
    ( prev += ( 1LL * X[ i ] - X[ i - 1 ] ) * i % MOD ) %= MOD;
    ( a += ( 1LL * X[ i ] - X[ i - 1 ] ) * i % MOD ) %= MOD;
  }
  for( int i = 1, prev = 0; i < M; ++i ){
    ( b += prev ) %= MOD;
    ( prev += ( 1LL * Y[ i ] - Y[ i - 1 ] ) * i % MOD ) %= MOD;
    ( b += ( 1LL * Y[ i ] - Y[ i - 1 ] ) * i % MOD ) %= MOD;
  }
  cout << 1LL * a * b % MOD << endl;
  return 0;
}