Segments on a Polygon [yukicoder No.743]

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

解法

https://yukicoder.me/submissions/289965

A[i]＜B[i]となるように整形しておく。
すると、線分iと線分jが交わる条件は

• A[j]＜A[i]かつA[i]＜B[j]＜B[i]　または
• A[i]＜A[j]＜B[i]かつB[i]＜B[j]

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

int N, M, A[101010], B[101010];
StaticHealthy2DSegTree st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i] >> B[i];

    vector<vector<pair<int, int>>> v(M);
    rep(i, 0, N) {
        if (A[i] > B[i]) swap(A[i], B[i]);
        v[A[i]].push_back({ B[i], 1 });
    }
    st.init(v);

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