MooFest

测评传送门

题意：

n 头牛互相对着叫，每头牛有一个 耳背度ai，位置bi;

使得两头牛可以互相听见需要的音量 abs(bi - bj)*max(ai , aj)

求所有牛可以互相听见的总音量

input

4
3 1
2 5
2 6
4 3

output

57

---

思路：

n方的暴力做法很显然，也很好写，但必挂！

于是就需要用数据结构来优化，我们采用树状数组。

n方做法复杂在于，每选定两个数，都需要比较谁更耳背，但是好在距离可以O(1) 得出。

耳背最大的牛对于其他牛来说肯定是选用它的耳背度，那我们以耳背排序，是不是就省去了判耳背的过程？

但问题又来了，间距又不好算了。

树状数组就在这时发挥作用啦 ~

我们先以坐标排序，用树状数组维护他们的坐标总和，像这样：

通过树状数组可以帮助我们维护区间信息，本题我们用它来维护区间坐标和、区间点的数量

麻烦的地方在于如何通过这些信息来O(1)地求出当前最耳背的牛和其他牛之间的 SUM(abs(pos))

以图中的样例为例：

当前最耳背的牛在 3 位置，设SUM为他到其他牛的间距和

SUM=(3-1)+(5-3)+(6-3)

我们发现在它后面的牛可以直接减去3，而它前面的牛则需倒过来取绝对值

设后缀的间距和为BAK,前缀间距和为PRE

BAK=SUM(2~4)-num(2~4)*pos(2)

PRE=pos(2)*num(1~2)-SUM(1~2)

代码表示：

BAK = quer(4,0)-quer(2,0) - pos(2)*( quer(4,1)-quer(2,1) )

PRE = pos(2)*quer(2,1) - quer(2,0)

ANS = (BAK+PRE)*val

code

#include<stdio.h> 
#include<algorithm> 
#define lowbit(x) x&(-x)
#define ll long long 
using namespace std;
const int MXN=21000;
struct node {
    int id,pos,val;
}a[MXN];
int n,c[MXN][2];
ll ans;

bool cvp(const node &p,const node &q) {return p.val<q.val;}
bool cop(const node &p,const node &q) {return p.pos<q.pos;}

void add(int x,int k,int d) {
    while(x<=n) {
        c[x][k]+=d;
        x+=lowbit(x);
    }
}

int quer(int x,int k) {
    int re=0;
    while(x) {
        re+=c[x][k];
        x-=lowbit(x);
    } 
    return re;
}

int main() 
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d%d",&a[i].val,&a[i].pos);    
        add(i,1,1);
    }
    sort(a+1,a+1+n,cop);
    for(int i=1;i<=n;++i) {
        a[i].id=i;
        add(i,0,a[i].pos);
    }
    sort(a+1,a+1+n,cvp);
    for(int i=n;i;--i) {
        add(a[i].id,1,-1);
        add(a[i].id,0,-a[i].pos);
        ans+=(long long)a[i].val*( quer(n,0) - 2*quer(a[i].id,0) + 
             a[i].pos*( quer(a[i].id,1)*2 - quer(n,1)) );
    }
    printf("%lld",ans);
    return 0;
}