EOJ3328. 时空交织的代价

题意


给定$n$个点和每个点在$x$轴上面的位置和每个点的权值,求出点对之间的费用总和。其中某两个点$i$,$j$之间的费用定义为$ | p_i - p_j | \times max\{v_i, v_j\} $。

题解


对于每个点,计算它左边权值小于它的点与它点对费用之和:\[{v_i}\sum\limits_j {({p_i} - {p_j})} = k{v_i}{p_i} - {v_i}\sum\limits_j {p_j} \]其中$k$是左边权值小于它的点的数量,$\sum\limits_j {p_j}$是它们的权值之和,可以用两个树状数组统计。右边同理。
首先按照$p$从小到大排序。对于每个点用树状数组分别统计出左右两边$v$比它小的$v$之和与数量,然后直接计算结果即可。

代码


#include <functional>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <climits>
#include <utility>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <cctype>
#include <bitset>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <new>
#include <map>
#include <set>
using namespace std;
//#pragma comment(linker, "/STACK:102400000,102400000")

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
typedef vector<int> vec;
typedef vector<vec> mat;
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define FI first
#define SE second
#define gcd(x, y) __gcd(x, y)
#define gcd3(x, y, z) __gcd(__gcd(x, y), z)

const double EPS = 1e-15;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = 200000 + 10;
const int MOD = 1000000007;

LL bit[MAXN], bit1[MAXN], n;

LL sum(int i) {
    LL s = 0;
    while (i > 0) {
        (s += bit[i]) %= MOD;
        i -= i & -i;
    }
    return s;
}

void add(int i, LL x) {
    while (i <= 10000) {
        (bit[i] += x) %= MOD;
        i += i & -i;
    }
}

LL sum1(int i) {
    LL s = 0;
    while (i > 0) {
        (s += bit1[i]) %= MOD;
        i -= i & -i;
    }
    return s;
}

void add1(int i, LL x) {
    while (i <= 10000) {
        (bit1[i] += x) %= MOD;
        i += i & -i;
    }
}

struct node {
    LL p, v;
    bool operator < (const node& rhs) const {
        return p < rhs.p;
    }
};

node a[MAXN];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &a[i].p);
    }
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &a[i].v);
    }
    sort(a, a + n);
    LL ans = 0;
    for (int i = 0; i < n; ++i) {
        LL cnt = sum(a[i].v);
        LL s = sum1(a[i].v);
        (ans += (((cnt * a[i].p - s) % MOD + MOD) % MOD) * a[i].v) %= MOD;
        add(a[i].v, 1);
        add1(a[i].v, a[i].p);
    }
    memset(bit, 0, sizeof bit);
    memset(bit1, 0, sizeof bit1);
    for (int i = n - 1; i >= 0; --i) {
        LL cnt = sum(a[i].v);
        LL s = sum1(a[i].v);
        (ans += (((s - cnt * a[i].p) % MOD + MOD) % MOD) * a[i].v) %= MOD;
        add(a[i].v, 1);
        add1(a[i].v, a[i].p);
    }
    memset(bit, 0, sizeof bit);
    memset(bit1, 0, sizeof bit1);
    for (int i = n - 1; i >= 0; --i) {
        LL cnt = sum(a[i].v) - sum(a[i].v - 1);
        LL s = ((sum1(a[i].v) - sum1(a[i].v - 1)) % MOD + MOD) % MOD;
        (ans -= (((s - cnt * a[i].p) % MOD + MOD) % MOD) * a[i].v) %= MOD;
        add(a[i].v, 1);
        add1(a[i].v, a[i].p);
    }
    printf("%lld\n", (ans % MOD + MOD) % MOD);
    return 0;
}

   转载规则


《EOJ3328. 时空交织的代价》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
一位长者关于保研的一些人生经验 一位长者关于保研的一些人生经验
经过三年的艰苦学习,终于也艰难保上研了,因此在此给学弟学妹们一点人生经验,粗鄙之见,大家随便看看。 学习 好好学习自然不用多说,自觉性是最重要的,作业不能拖拉,不要拖到最后一刻才做作业。就拿我自己说吧,我每次上完课都会立即把上课讲的再看一
2017-09-19
本篇 
EOJ3328. 时空交织的代价 EOJ3328. 时空交织的代价
题意 给定$n$个点和每个点在$x$轴上面的位置和每个点的权值,求出点对之间的费用总和。其中某两个点$i$,$j$之间的费用定义为$ | p_i - p_j | \times max\{v_i, v_j\} $。 题解 对于每个点,计算它左
2017-09-19
  目录