ARC031 C問題 積み木

積み木を並べ替える問題。
BIT使えばO(nlogn)ですね、はい。
問題をもっと簡単に表せる方法を頑張って探せば、こういう問題は楽。
難しく考えない。

ちなみに、最初 int res = 0;と書いていて値が大きい時オーバーフローして死んだ。
int は2*1e9くらいまでしか計算できないですね。はい。
もうこういうので悩むのは嫌なので毎回long long 使おうな。

struct BinaryIndexedTree{
    int N;
    std::vector<int> bit; //1-indexed つまり1~Nを使う
    BinaryIndexedTree(int n): N(n), bit(n+1, 0){}
    void add(int a, int w){
        for(int x = a; x <=N; x+=x&(-x)) bit[x] += w;
    }
    int sum(int a){ //1~aまでsum
        int ret = 0;
        for(int x = a; x>0; x-=x&(-x)) ret += bit[x];
        return ret;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N; cin >> N;
    int B[N+1];
    BinaryIndexedTree bit(N+5);
    map<int, int> mp;
    for(int i=1; i<=N; i++){
        cin >> B[i];
        bit.add(i, 1);
        mp[B[i]] = i;
    }
    ll res = 0;
    for(int i=1; i<=N; i++){
        int now = mp[i];
        int tmp = bit.sum(now);
        int low = tmp-1;
        int high = bit.sum(N)-tmp;
        res += min(low, high);
        bit.add(now, -1);
    }
    cout << res << endl;
}