にゃんにゃんにゃん 猫の挨拶 [yukicoder No.742]

https://yukicoder.me/problems/no/742

解法

https://yukicoder.me/submissions/289941

ある猫についてiからM[i]へ移動するときにすれ違う猫の条件は

• [0,i)にいる猫で到着先が[M[i], N) または
• [i+1,N)にいる猫で到着先が[0,M[i]]

である。
　
そのため、長方形区間総和を求めることができれば、答えが求まる。
いろいろ方法がある「WaveletMatrix」「2Dセグメントツリー」「BITを使ってもできそう」
自分の実装では2Dセグメントツリーを使った。
　
この数え方だと猫aと猫bがすれ違うのを(a,b)と(b,a)で重複して数えているので、
組み合わせ数を÷2して答える。

int N, M[30101];
StaticHealthy2DSegTree st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> M[i], M[i]--;
    vector<vector<pair<int, int>>> v(N);
    rep(i, 0, N) v[i].push_back({ M[i], 1 });
    st.init(v);

    ll ans = 0;
    rep(i, 0, N) {
        ans += st.get(0, i, M[i], N);
        ans += st.get(i + 1, N, 0, M[i] + 1);
    }
    cout << ans / 2 << endl;
}