MooFest

题目大意

分析

其实我们发现这个十分不好维护

就是说，如果已经保证了，那么原式可以写为

这个按照从大到小就可以了吧

那么就是的问题了

这个看看数据，这个大概是需要一个的复杂度

那么发现像什么线段树，树状数组之类的高级数据结构就可以维护

就分成两种情况，一种是的，一种是的

那就分别求和，那么就可以写成这样

细节

这个用了一个十分易懂的方式来维护

那就是先按照从小到大排序

用树状数组一个点一个点插入，记录一下每头牛的的排序，方便下文的删除操作

然后再按从大到小排序

然后每次就查询完了就从树状数组中把这头牛删掉

然后重载了一下运算符，操作可能会方便一些吧

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int p = 1e9 + 7;

int n;
ll ans(0);
struct node{int v, x, p;}c[maxn];

inline bool cmpx(node x, node y)
{
    return x.x < y.x;
}

inline bool cmpv(node x, node y)
{
    return x.v > y.v;
}

#define lowbit(x) (x & -x)
int tree[maxn], cnt[maxn];
inline void add(int x, int v, int p)
{
    while (x <= n) {
        tree[x] += v;
        cnt[x] += p;
        x += lowbit(x);
    }
}

inline pair<int, int> query(int x)
{
    int ans(0), cur(0);
    while (x) {
        ans += tree[x];
        cur += cnt[x];
        x -= lowbit(x);
    }
    return make_pair(ans, cur);
}

#define sum first
#define num second

pair <int, int> operator - (pair <int, int> a, pair<int, int> b)
{
    return make_pair (a.sum - b.sum, a.num - b.num);
}

inline pair<int, int> query(int l, int r)
{
    return query(r) - query(l);
}

int main()
{  
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i) scanf ("%d %d", &c[i].v, &c[i].x);
    sort (c + 1, c + n + 1, cmpx);
    for (int i = 1; i <= n; ++i) add(i, c[i].x, 1), c[i].p = i;
    sort (c + 1, c + n + 1, cmpv);
    for (int i = 1; i <= n; ++i) {
        pair <int, int> r = query(c[i].p, n), l = query(c[i].p - 1);
        ans += 1ll * c[i].v * (r.sum - r.num * c[i].x + l.num * c[i].x - l.sum);
        add(c[i].p, -c[i].x, -1);
    }
    printf ("%lld\n", ans);
}