P6067 [USACO05JAN]Moo Volume S

happybob · 2022-02-15 18:44:35 · 题解

题意

给定一个 n 个元素的序列 a，求出 (\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \lvert a_j-a_i \rvert ) \times 2。

解法

我有一个独特的方法。

首先 O(n^2) 明显只能过任务 0，并且只能得 1 分，那么我们考虑式子中 \sum_{j=i+1}^{n} \lvert a_j-a_i \rvert 的特性，第一个想法是 \sum_{j=i+1}^{n} \lvert a_j-a_i \rvert = (\sum_{j=i+1}^n a_j) - [(n-i) \times a_i]，但是明显需要排序。

那么排序完后大家都是拆式子，但是我们可以看出 (\sum_{j=i+1}^n a_j) 可以线段树维护，所以排序 O(n \log n)，获取答案 O(n \log n)，总复杂度 O(n \log n)，足以通过，当然其他解法可能更快，例如前缀和可以做到 O(n) 获取答案。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

#define int long long

const int N = 1e5;

int a[N];

struct Node
{
    int l, r, sum;
};

Node tree[N << 2ll];

void push_up(int u)
{
    tree[u].sum = tree[u << 1ll].sum + tree[u << 1ll | 1ll].sum;
}

void build(int u, int l, int r)
{
    tree[u] = { l, r };
    if (l == r) tree[u].sum = a[r];
    else
    {
        int mid = (l + r) >> 1ll;
        build(u << 1ll, l, mid);
        build(u << 1ll | 1ll, mid + 1ll, r);
        push_up(u);
    }
}

int query(int u, int l, int r)
{
    if (tree[u].l >= l && tree[u].r <= r) return tree[u].sum;
    int mid = (tree[u].l + tree[u].r) >> 1ll, s = 0;
    if (l <= mid) s = query(u << 1ll, l, r);
    if (r > mid) s += query(u << 1ll | 1ll, l, r);
    return s;
}

signed main()
{
    int n, ans = 0, sum = 0;
    scanf("%lld", &n);
    for (int i = 1ll; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }
    sort(a + 1ll, a + n + 1ll);
    build(1ll, 1ll, n);
    for (int i = 1ll; i <= n; i++)
    {
        sum = query(1ll, i + 1ll, n);
        ans += sum - a[i] * (n - i);
    }
    printf("%lld\n", ans << 1ll);
    return 0;
}