Description

给定两个长度为 $n$ 的序列 $v_i,x_i$，定义一个点对 $(i,j)$（$i \ne j$）的价值 $f(i,j)$ 为 $\max(v_i,v_j) \times |x_i-x_j|$，求：

$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n f(i,j)[i \ne j]$$

Solution

很难想象这只是一个绿题，可能拿树状数组做会舒服一点吧，这里介绍分治做法。

我们把 $\displaystyle \sum\limits_{i=1}^n \sum\limits_{j=1}^n f(i,j)[i \ne j]$ 先拆成 $\displaystyle \sum\limits_{i=1}^n\sum\limits_{j=1}^n \max(v_i,v_j)[i \ne j]$ 和 $\displaystyle \sum\limits_{i=1}^n \sum\limits_{j=1}^n |x_i-x_j|[i \ne j]$，看看分别怎么计算：

• $\displaystyle \sum\limits_{i=1}^n\sum\limits_{j=1}^n \max(v_i,v_j)[i \ne j]$ 我们把 $v_i$ 升序排列一下，那么第 $i$ 个数的贡献即为前 $i-1$ 个数。
• $\displaystyle \sum\limits_{i=1}^n \sum\limits_{j=1}^n |x_i-x_j|[i \ne j]$ 我们把 $x_i$ 升序排列一下，那么定 $j$ 为右端点，下面这一段就可以如下化简：

$$\begin{aligned}\sum\limits_{i=1}^{j-1}|x_i-x_j|&=\sum\limits_{i=1}^{j-1}x_j-x_i\\&=\sum\limits_{i=1}^{j-1}x_j -\sum\limits_{i=1}^{j-1}x_i\\&=x_j \times (j-1)-sum_{j-1}\end{aligned}$$

其中 $sum_i$ 为前缀和。

那把这两个融合起来怎么搞呢？我们可以用结构体输入这两个序列，以 $v$ 为第一关键字先把序列进行排序。

现在对于区间 $[l,r]$ 计算他的贡献，这一段区间的 $v$ 是已经排好序的，所以考虑分治，将区间分为两半 $[l,mid]$ 和 $[mid+1,r]$，可以通过递归算出贡献在 $[l,mid]$ 的和贡献在 $[mid+1,r]$ 的，接下来要算的就是有贡献的跨越这两个区间的。

我们在 $[mid+1,r]$ 中枚举 $j$ 作为贡献的右界，算 $[l,j]$ 的贡献，并将其加起来作为跨区间的贡献和。将其分拆为 $v$ 和 $x$ 两部分计算：

• $v$，既然排过序了那么全部都是 $v_j$。
• $x$，其中 $[l,j]$ 的贡献会有一个位置 $i$ 使得 $i$ 是最后一个 $a_i(x) \le a_j(x)$ 的，那么区间 $[l,j]$ 的贡献就可以如下计算（$sumx_{[l,r]}$ 为 $a_{[l,r]}(x)$ 的和）：

$$\begin{aligned}x_j-x_l+x_j-x_{l+1}+\cdots+x_j-x_i+x_{i+1}-x_j+\cdots+x_{mid}-x_j&=\sum\limits_{k=l}^i x_j-x_k+\sum\limits_{k=i+1}^{mid} x_k-x_j\\&=\sum\limits_{k=l}^i x_j-\sum\limits_{k=l}^i x_k+\sum\limits_{k=i+1}^{mid} x_k-\sum\limits_{k=i+1}^{mid} x_j\\&=x_j \times (i-l+1)-sumx_{[l,i]}+sumx_{[i+1,mid]}-x_j \times (mid -i)\end{aligned}$$

通过预处理前缀和这个是可以 $\mathcal O(1)$ 求的，也就是对于一个 $j$，他对答案的贡献为：

$$v_j \times (x_j \times (i-l+1)-sumx_{[l,i]}+sumx_{[i+1,mid]}-x_j \times (mid -i))$$

但注意，能将其如上计算的前提是 $[l,mid]$ 和 $[mid+1,r]$ 分别按照 $x$ 进行排序。

我们都知道有归并排序，所以可以处理完上面这些之后再将 $[l,r]$ 以 $x$ 为关键字排一下序。我们不用在处理答案前排序的原因应该很简单，因为有递归函数帮我们处理 $[l,mid]$ 和 $[mid+1,r]$ 的顺序问题，只需要为 $[l,r]$ 外面的区间服务即可。

代码放的是处理贡献的部分。

Code

int mid = (l + r) / 2;
solve(l, mid);
solve(mid + 1, r);
memset(sum, 0, sizeof(sum));
for (int i = l; i <= r; i++) sum[i] = sum[i - 1] + a[i].x;
int i = l - 1;
for (int j = mid + 1; j <= r; j++) {
	while (a[i + 1].x <= a[j].x && i < mid)
		i++;
	ans += a[j].v * ((i - l + 1) * a[j].x - sum[i] + sum[mid] - sum[i] - (mid - i) * a[j].x);
}

树状数组

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10, M = 1e6;
struct node{int v,x;}a[N];
int c[2][M+10];
void add(int x,int k,int *cc){for(;x <= M;x +=x&-x)cc[x] += k;}
int getsum(int x,int *cc){
    int res = 0;
    for(;x;x -= x&-x)res += cc[x];
    return res;
}

signed main(){
    int n;scanf("%lld",&n);
    for(int i = 1;i <= n;i ++)scanf("%lld%lld",&a[i].v,&a[i].x);
    sort(a + 1,a + n + 1,[](node x,node y){return x.v < y.v;});
	memset(c,0,sizeof(c));
	int ans = 0,presum=0;
    for(int i = 1;i <= n;i ++){
        int num = getsum(a[i].x,c[0]);
        int sum = getsum(a[i].x,c[1]);
        ans += (num * a[i].x - sum) * a[i].v;//小于它
        ans += ((presum - sum) - (i - num - 1) * a[i].x) * a[i].v;//大于它
        add(a[i].x,1,c[0]);//更新
        add(a[i].x,a[i].x,c[1]);
        presum += a[i].x;//前缀和
    }
    printf("%lld\n",ans);
    return 0;
}

归并排序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e4+10;
struct node{LL v, x;} a[N], b[N];
LL ans;
bool cmp(node n1, node n2){
    return n1.x>n2.x;
}
void mergesort(int l, int r){
    if(l==r) return ;
    int mid=(l+r)/2;
    mergesort(l, mid); mergesort(mid+1, r);
    int lp=l, rp=mid+1, len=0; LL suml=0, sumr=0;
    for(int i=l; i<=mid; i++)   suml+=a[i].x;
    for(int i=mid+1; i<=r; i++) sumr+=a[i].x;
    while(lp<=mid && rp<=r){
        if(a[lp].v>a[rp].v){
            ans+=a[lp].v*abs((r-rp+1)*a[lp].x-sumr);
            suml-=a[lp].x;
            b[++len]=a[lp++];
        }
        else{
            ans+=a[rp].v*abs(suml-(mid-lp+1)*a[rp].x);
            sumr-=a[rp].x;
            b[++len]=a[rp++];
        }
    }
    while(lp<=mid) b[++len]=a[lp++];
    while(rp<=r)   b[++len]=a[rp++];
    for(int i=l; i<=r; i++) a[i]=b[i-l+1];
}
int main(){
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld%lld", &a[i].v, &a[i].x);
    sort(a+1, a+n+1, cmp);
    ans=0; mergesort(1, n);
    printf("%lld\n", ans);
    return 0;
}