MooFest

Posted on Edited on In Word count in article: 552 Reading time ≈ 2 mins.
MooFest

MooFest

题目大意

分析

其实我们发现这个\(\max\)十分不好维护

就是说，如果已经保证了\(v_i\ge v_j\)，那么原式可以写为

\[ \sum_{i=1}^nv_i\sum_{j=1}^ndis(i,j) \]

这个按照\(v_i\)从大到小就可以了吧

那么就是\(\sum_{j=i+1}^ndis(i,j)\)的问题了

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

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

就分成两种情况，一种是\(x_p>x_i\)的，一种是\(x_p < x_i\)的

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

\[ sum\{x_p[x_p>x_i]\}-cnt\{[x_p>x_i]\}*x_i+cnt\{[x_p<x_i]\}*x_i-sum\{x_p[x_p<x_i]\} \]

细节

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

那就是先按照\(x_i\)从小到大排序

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

然后再按\(v_i\)从大到小排序

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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);
}