Beta Round #57-E: Enemy is weak

keyword

反転数　BIT　C++

問題概要

長さN(<10^6)の互いに異なる数列が与えられる。このとき、(i,j,k) s.t. ia[j]>a[k]を満たす組がいくつあるか求める問題。

解法

反転数に似た概念の問題。解き方も普通の反転数を求めるときとかなり似通っている。まず前処理として座標圧縮っぽい方法で数列aを[1..N]のpermutationにする。数列cをc[i] = #{j | a[i]>a[j], ia[j]} c[j]を加算していく。これもBITでできる。

const int MAX_N = 1000009;
int N;
int bs[MAX_N];
int as[MAX_N];
int64 cs[MAX_N];
int64 bit[2][MAX_N];

int64 sum(int which, int i){
    int64 s = 0;
    while(i>0){
        s += bit[which][i];
        i -= i & -i;
    }
    return s;
}

void add(int which, int i, int64 x){
    while(i<=N){
        bit[which][i]+=x;
        i += i & -i;
    }
}

void init(){
    for(int i=0; i<N; i++) as[i] = bs[i];
    sort(bs,bs+N);
    for(int i=0; i<N; i++){
        as[i] = (lower_bound(bs, bs+N, as[i]) - bs) + 1;
    }
    for(int i=N-1; i>=0; i--){
        int64 nn = sum(0,as[i]-1);
        cs[i] = nn;
        add(0,as[i],1);
    }
}

int64 solve(){
    init();
    int64 ans = 0;
    for(int i=N-1; i>=0; i--){
        int64 nn = sum(1,as[i]-1);
        ans += nn;
        add(1,as[i],cs[i]);
    }
    return ans;
}

int main(){
    scanf("%d",&N);
    for(int i=0; i<N; i++){
        scanf("%d",bs+i);
    }