nu50218 blog

017 - Crossing Segments（★7）の別解

 kyopro  984  2 分

競プロ典型90問「017 - Crossing Segments（★7）」の別解になります。 本質的には同じことをやっていたらすみません。

問題

問題文

演習上に $N$ 個の点があり、時計回りに $1,2,\dots,N$ と番号づけられています。 また、 $M$ 本の線分があり、線分 $i$ は点 $L_i$ と 点 $R_i$ を結んでいます。

線分 $s, t$ が端点以外で交わるような、 $(s, t) \ (1 \leq s < t \leq M)$ の組の数を求めてください。

https://atcoder.jp/contests/typical90/tasks/typical90_q より引用

制約

  • $N, M \leq 3 \times 10^5$

別解

考察

円周を $N$ 頂点の重みなし無向サイクルだとみなします。 そして、「線分 $i$ の幅」 を $\min(R_i - L_i, N - (R_i - L_i))$ で定義します。 これは、円周を $N$ 頂点のサイクルとみなしたとき、頂点 $L_i$ から $R_i$ の最短経路上のパスの数に等しいです。

さて、幅が最小の線分 $i$ を考えます。 線分 $j$ が線分 $i$ と端点以外で交わるとき、以下が成り立ちます。

  • 「頂点 $L_i$ から $R_i$ の最短経路」上（$L_i, R_i$を除く）に線分 $j$ の端点が存在する。

一方で、幅の最小性より、以下も成り立ちます。

  • 「頂点 $L_i$ から $R_i$ の最短経路」上（$L_i, R_i$を除く）に端点を持つ線分について、もう片方の端点は「頂点 $L_i$ から $R_i$ の最短経路でない方のシンプルパス」上（$L_i, R_i$を除く）にある。

上述の２つの事実から、少し考えると、以下の２つの個数が等しいことがわかります。

  • 線分 $i$ と端点以外で交わる線分の個数。
  • 「頂点 $L_i$ から $R_i$ の最短経路」上にある端点の個数。

解法

以上の考察を用いると、次の方法で正しい答えが得られることがわかります。

  1. $\mathrm{ans}$ を $0$ とする。

  2. 以下を線分が無くなるまで繰り返す。

    1. 幅が最小の線分を１つ選び、 $i$ とする。
    2. 「頂点 $L_i$ から $R_i$ の最短経路」上にある端点の個数を、 $\mathrm{ans}$ に加える。
    3. 線分 $i$ を削除する。

  3. $\mathrm{ans}$ を出力する。

上記は、セグメントツリーを使うことで、 $\Theta(M (\log M + \log N))$ 時間で計算することができます。

ソースコード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <bits/stdc++.h>

#include <atcoder/segtree.hpp>

using namespace std;

struct line {
    int width;
    int L, R;
};

int op(int a, int b) {
    return a + b;
}

int e() {
    return 0;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<line> lines;

    for (int i = 0; i < M; i++) {
        int L, R;
        cin >> L >> R;

        L--;
        R--;

        int width1 = R - L;
        int width2 = L + N - R;

        if (width1 <= width2) {
            lines.push_back({width1, L, R});
        } else {
            lines.push_back({width2, R, L});
        }
    }

    sort(lines.begin(), lines.end(), [](line a, line b) {
        return a.width < b.width;
    });

    atcoder::segtree<int, op, e> st(N);
    for (auto&& [_, L, R] : lines) {
        st.set(L, st.get(L) + 1);
        st.set(R, st.get(R) + 1);
    }

    long long ans = 0;

    for (auto&& [_, L, R] : lines) {
        if (L < R) {
            ans += st.prod(L + 1, R);
        } else {
            ans += st.prod(L + 1, N);
            ans += st.prod(0, R);
        }

        st.set(L, st.get(L) - 1);
        st.set(R, st.get(R) - 1);
    }

    cout << ans << endl;
}

提出: https://atcoder.jp/contests/typical90/submissions/37691943

関連記事: