SPOJ: Boba Inversion

#include <bits/stdc++.h>

using namespace std;
const int N = 5e3 + 10;
vector <int> num;
int ar[N], idx[N], fw[N], ques[N][N];
int n, sz;

void Update(int pst){
    for(int i=pst;i<=sz;i+=i&-i)
        fw[i] ++;
}

int Sum(int pst, int sum = 0){
    for(int i=pst;i>=1;i-=i&-i)
        sum += fw[i];
    return sum;
}

int main(){

    scanf("%d", &n);

    for(int i=1;i<=n;i++){
        scanf("%d", &ar[i]);
        num.push_back(ar[i]);
    }

    sort(num.begin(), num.end());
    num.resize( unique(num.begin(), num.end()) - num.begin());
    sz = num.size();

    for(int i=1;i<=n;i++){
        int l = 0, r = sz - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(num[mid] == ar[i]){
                idx[i] = mid + 1;
                break;
            }
            else if(num[mid] < ar[i])
                l = mid + 1;
            else
                r = mid - 1;
        }
    }

    for(int i=1;i<=n;i++){
        int ans = 0;
        for(int j=i;j<=n;j++){
            /// [ i , j ]
            ans += Sum(sz) - Sum(idx[j]);
            ques[i][j] = ans;
            Update(idx[j]);
        }
        for(int j=1;j<=sz;j++)
            fw[j] = 0;
    }

    int Q;
    scanf("%d", &Q);

    for(int q=1;q<=Q;q++){
        int s, e;
        scanf("%d %d", &s, &e);
        printf("%d\n", ques[s][e]);
    }

    return 0;
}