PKU1990

MooFest

■問題
直線上にいるN匹の牛の聴力と座標が与えられる。
異なる2匹の牛の座標の差の絶対値と聴力の大きい方を掛けたものをすべての組み合わせに対して求めその総和を出力せよ。

■解法
すべての組み合わせを試す際、聴力に対して昇順ソートすることで「i番目の牛の聴力*i番目以前のすべての牛の距離の差の総和」をすべての牛に対してやることで聴力の最大を気にする必要がなくなる。よって牛の距離の差の総和を高速に求める必要がある。

距離の差は自分の座標をX,相手をxiとすると相手が小さい場合はX-xi、大きい場合はxi-Xとなり、
小さい牛の総和は X-x1 + X-x2 + ・・・ + X-xn = X*n - (x1 + x2 + ・・・ + xn)
大きい牛の総和は x1-X + x2-X + ・・・ + xn-X = (x1 + x2 + ・・・ + xn) - X*n
という式によって求めることができる。

その式の括弧の中は、配列の添字を座標と対応させたBITによって求める。
i番目以前というのは使ったものから順番にBITに値を追加していくことで解決できる。

小さい牛の数、大きい牛の数もわからなくてはならないので総和とは別にもう一つBITを作り、牛の数もBITで求める。

int型に収まらないことがあることにも注意する。

■ソース

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <map>
#define F first
#define S second
using namespace std;
typedef pair<int,int> P;
int n;

long long l[22222],c[22222];
long long sum(long long a[],int i){
  long long s = 0;
  while(i > 0){
    s += a[i];
    i -= i & -i;
  }
  return s;
}

void add(long long a[],int i,int x){
  while(i <= 20000){
    a[i] += x;
    i += i & -i;
  }
}

P m[22222];
int main(void){
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> m[i].F >> m[i].S;
  }
  sort(m,m+n);

  long long res = 0;
  for(int i = 0; i < n; i++){
    long long sl = sum(l,m[i].S);
    long long bl = sum(l,20000);
    long long sc = sum(c,m[i].S);
    res += m[i].F*(m[i].S*sc-sl+bl-sl-m[i].S*(i-sc));
    add(c,m[i].S,1);
    add(l,m[i].S,m[i].S);
  }
  printf("%lld\n",res);
}