P2345 奶牛集会

题目背景

MooFest, 2004 Open

题目描述

约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很

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

输入输出格式

输入格式：

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

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

输出格式：

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

---

对于这个题，要求的即为 \(\sum_{i=1}^n V_i*\sum_{V_j<V_i} |x_i-x_j|\)

对于音量\(V\)，我们可以排序来做以消除影响。

但对于带绝对值的距离，就不太好处理了。

我们考虑去掉绝对值。

\(\sum_{i=1}^n V_i*(\sum_{V_j<V_i,x_i>x_j} (x_i-x_j)*\sum_{V_j<V_i,x_i<x_j} (x_j-x_i))\)

\(\Rightarrow \sum_{i=1}^n( V_i*(\sum_{ V_j<V_i,x_i<x_j }x_j )-V_i*(\sum_{ V_j<V_i,x_i>x_j }x_j )+x_i*(k_1-k_2) )\)(其中，\(k_1\)存储位置在\(x_i\)左边的点的个数，\(k_2\)右边)

我们使用两个树状数组\(c1\)和\(c2\)分别维护\(1\)~\(n\)的坐标之和，和\(1\)~\(n\)的点的个数。其中\(1\)~\(n\)表示按位置离散化的值。

我们将\(v\)从小到大排序并将这个点加入树状数组即可。

---

code:

#include 
    
     #include 
     
      #define ll long longusing namespace std;const ll N=20010;ll c1[N],c2[N];//奶牛个数，奶牛距离和ll n;struct node{    ll x,v,i;    bool friend operator <(node n1,node n2)    {        return n1.x
     
    

---

2018.6.2