Chaos of the Snuke World [COLOCON -Colopl programming contest 2018- Final D]

https://beta.atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_d

前提知識

• 転倒数
• BIT

解法

https://beta.atcoder.jp/contests/colopl2018-final/submissions/1997404

まず石版の順番であるが、max(A,B)で昇順ソートしたものが最適解っぽい。
hamkoさんの解説にかかれている理由がとても説得力がある。
自分の場合はO(2^N)解を書いてサンプル1,2で確認したら合ってたから採用した。
　
ここからが難しい。
今回は「スワップ回数の期待値を2^N倍した値」を求めているが、これは「2^N通りの場面におけるスワップ回数の総和」を求めていることになる。
ソートのためのスワップ回数は転倒数とも呼ばれる。
転倒数の計算方法はいくつかあるが、「ia[j]となるi,jの組の組合せ」とも言える。
この条件を使って数え上げていこう。
　
i,jのうちjを全探索する。
「BIT[x] := [0,j)の範囲の中でA,Bで値がxである個数」としてBITを使っていく。
これを順番に更新していくことにすると、a[i]＞a[j]となるjの個数はBIT[a[j] + 1, inf)で求められる。
あとは、2^Nの状態の中でこの場面が何回出てくるかであるが、これはi,j番目以外の状態全てであるため2^(N-2)通りある。
よって、この2つの積を計算していき、総和を取ると答えになる。

int N;
vector<pair<int, int>> v;
BIT<mint> bit;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int a, b; cin >> a >> b;
        if (a < b) swap(a, b);
        v.push_back({ a, b });
    }
    sort(v.begin(), v.end());
    bit.init(N * 2 + 1);
 
    mint po = mint(2) ^ (N - 2);
    mint ans = 0;
    rep(i, 0, N) {
        int a = v[i].first;
        int b = v[i].second;
        // a >= b
        
        ans += bit.get(b + 1, N * 2 + 1) * po;
        
        bit.add(a, 1);
        bit.add(b, 1);
    }
    cout << ans << endl;
}