JOI春合宿2014 Day1-2 Growing Vegetables is Fun

解法

この問題いろいろなコンテストで再出題されてる気がする。
その草を昇順降順に並べたときのコストをBIT使って素早く求めておいて、 その情報を元にそのIOI草を左か右どっちに配置するか比べる。

ソース

#include<bits/stdc++.h>  
using namespace std;
const int INF = 1 << 30;

struct BIT{
  vector< int > bit;
  size_t sz;
  int sum(int idx){
    int sum = 0;
    for( ; idx ; idx -= idx & -idx) sum += bit[idx];
    return sum;
  }
  void add(int idx, int value){
    for( ; idx < bit.size(); idx += idx & -idx) bit[idx] += value;
  }
  BIT(int size):sz(size){
    bit.resize(size, 0);
  };
};
typedef pair< int , int > Pi;
int main(){
  int n;
  cin >> n;
  vector< int > vc(n);
  vector< Pi > cp(n);
  BIT bit1(n + 1), bit2(n + 1);
  for(int i = 0; i < n; ++i){
    scanf("%d", &vc[i]);
    cp[i] = make_pair( vc[i], i);
  }
  sort( cp.begin(), cp.end());

  int cnt = 1;
  for(int i = 0; i < cp.size(); ){
    do{
      vc[cp[i].second] = cnt;
      ++i;
    } while(i < cp.size() && cp[i - 1].first == cp[i].first);
    ++cnt;
  }

  BIT& b = bit1;
  vector< int > hoge[2];
  for(int j = 0; j < 2; ++j){
    hoge[j].resize(n);
    for(int i = 0; i < n; ++i){
      hoge[j][i] = i - bit1.sum(vc[i]);
      bit1.add( vc[i], 1);
    }
    reverse( vc.begin(), vc.end());
    b = bit2;
  }
  long long count = 0;
  for(int i = 0; i < n; ++i){
    count += min( hoge[0][i], hoge[1][n - 1 - i]);
  }
  printf("%lld\n", count);
}