[USACO 04OPEN]MooFest

Description

约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i 头奶牛的坐标为Xi，没有两头奶牛的坐标是相同的。奶牛们的叫声很大，第i 头和第j 头奶牛交流，会发出max{Vi; Vj}×|Xi − Xj | 的音量，其中Vi 和Vj 分别是第i 头和第j 头奶牛的听力。假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。

Input

• 第一行：单个整数N，1 ≤ N ≤ 20000

• 第二行到第N + 1 行：第i + 1 行有两个整数Vi 和Xi，1 ≤ Vi ≤ 20000; 1 ≤ Xi ≤ 20000

Output

• 单个整数：表示所有奶牛产生的音量之和

Sample Input

4
3 1
2 5
2 6
4 3

Sample Output

题解

开四个树状数组。

第一个为以 $V$ 为关键词，牛个数的前缀；

第二个为以 $V$ 为关键词， $X$ 的前缀；

第三个为以 $V$ 为关键词， $V$ 的前缀；

第四个为以 $V$ 为关键词， $X\times V$ 的前缀。

然后扫一遍随便乱搞就好了。

 //It is made by Awson on 2018.1.20

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Abs(a) ((a) < 0 ? (-(a)) : (a))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

 #define writeln(x) (write(x), putchar('\n'))

 #define lowbit(x) ((x)&(-(x)))

 using namespace std;

 const int N = ;

 void read(int &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 void write(LL x) {

     if (x > ) write(x/);

     putchar(x%+);

 }

 int n;

 struct tt {

     int v, x;

     bool operator < (const tt &b) const {return x < b.x; }

 }a[N+];

 struct bittree {

     LL c[N+];

     void add(int x, int val) {for (; x <= N; x += lowbit(x)) c[x] += val; }

     LL query(int x) {

     LL ans = ;

     for (; x; x -= lowbit(x)) ans += c[x];

     return ans;

     }

 }T1, T2, T3, T4; //T1 tol, T2 tolx, T3 tolt, T4 tolx*t

 void work() {

     read(n); for (int i = ; i <= n; i++) read(a[i].v), read(a[i].x);

     sort(a+, a+n+); LL ans = ;

     for (int i = ; i <= n; i++) {

     ans += (T1.query(a[i].v)*a[i].x-T2.query(a[i].v))*a[i].v;

     ans += (T3.query(N)-T3.query(a[i].v))*a[i].x-(T4.query(N)-T4.query(a[i].v));

     T1.add(a[i].v, ), T2.add(a[i].v, a[i].x), T3.add(a[i].v, a[i].v), T4.add(a[i].v, a[i].x*a[i].v);

     }

     writeln(ans);

 }

 int main() {

     work();

     return ;

 }

秒客网