MooFest

其实，我英语水平垃圾的很。。。
题目大意：
给你坐标和每个坐标的权值，题目求n个坐标两两之间的“声音权值”的和，其中任意两个点之间的“声音权值” = 距离*max(两点的权值）。
1.暴力求解法：容易想，也容易TLE
2.树状数组：
我们在处理的过程中，按照权值大小升序排序，可以省略掉取max的步骤。
对于排序之后的第i个元素，设坐标为,权值为，那么对于任意的,都有，在处理第i个元素的时候，权值都是取的。其中，权值小于的点有个，设他们在集合中。
但是这样之后，坐标x是无序的，设中坐标小于的点有个，坐标的和是;
大于的就有个,（中间要去掉一个本身），坐标的和是
然后求距离，坐标小于的点的距离和是,坐标大于的点的距离和是，权值和就是。
这个过程其实是可以转化为区间和的，例如，求中坐标小于的坐标和，其实就是以坐标为树状数组的下标，求的区间和。其他详细看代码。
code：

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N = 20000+5;
//const ll inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod =  199999;
const double eps=1e-7;
//const int tmp=31;

int sn[N],sx[N];//坐标和，坐标数量
struct node
{
    int v,x;
    bool operator<(const node& b)const{
        return v<b.v;
    }
}a[N];
int lowebit(int x){
  return x&(-x);
}
void add(int i,int v){

   while(i<=20000){
      sx[i]+=v;
      sn[i]++;
      i+=lowebit(i);
   }
}
ll ask(int i,int op){//op是0的时候计算坐标和，1的时候计算坐标数量

  ll s=0;
  while(i>0){
    if(!op) s+=sx[i];
    else s+=sn[i];
    i-=lowebit(i);
  }
  return s;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].v,&a[i].x);
    sort(a+1,a+n+1);
    ll s=0;
    for(int i=1;i<=n;i++){
        ll cor=ask(a[i].x,0);
        ll cor2 = ask(20000,0);//x的最大值是20000，所以用它当作区间的右端点，
                               //最后减去小于a[i].x的坐标和，剩下的才是真正大于a[i].x的坐标和，之后再求距离。
        ll num=ask(a[i].x,1);
        s += a[i].v*(num*a[i].x-cor)+a[i].v*(cor2-cor-(i-num-1)*a[i].x);
        add(a[i].x,a[i].x);
    }
    printf("%lld\n",s);
    return 0;
}

poj不支持万能头文件！！！