考察
各chordの端点をA_i<B_iに揃え、円を1と2Nの間で切る。二本が交差するのは端点がA_i<A_j<B_i<B_jのように交互に現れる場合であり、交差がなければ開いたchord区間は互いにdisjointか完全にnestedになる。
採用する候補: 端点を順に走査し、open中のchordをstackで照合する
非交差ならnested区間の閉じ順は必ずLIFOであり、一度の線形走査で交差を検出できる。
棄却する候補: 全chord pairの端点順を比較する
pair数がO(N^2)でN=2×10^5に対応できない。
左端を見たchordをpushし、右端iを見た時にstack topがiでなければ、iの内側で開始した別chordがまだ閉じておらずA_i<A_j<B_i<B_jとなる。逆にtopが常に一致すれば全区間は正しくnestedし交差しない。
各chordで端点をmin/maxにし、位置1,…,2Nにchord IDと左/右種別を記録する。左端ならIDをpush、右端ならpopしたIDと比較し、不一致ならYesを即出力する。最後まで一致すればNo。
典型の発動条件
円環のcut展開
発動条件: 円周上の端点の交互配置を線形順序で判定したい。
端点間の切れ目で円を開き、各chordを区間の開閉eventとして扱う。
括弧列としてのstack判定
発動条件: 区間族が交差せずnested/disjointであるかを調べたい。
chord IDを括弧種類とみなし、closeが直近openと一致するか確認する。
問題固有の要素
全端点がdistinctなので、非交差chord配置の端点列はID付きの正しい括弧列と同値になる。
別の問題へ持ち帰る視点: 区間の部分重なり検出は、laminar族なら開閉eventがLIFOになることを使える。
正当性
二chordが交差する必要十分は円周端点順が交互になること。開いた区間がnested/disjointなら右端は最新左端のchordを閉じるのでstackが一致する。右端でtop不一致なら先に開いたchordの内側で別chordが開いたまま外へ続く交互順を具体的に得る。従って一度でも不一致が交差、最後まで一致なら非交差。
実装上の注意
- 各pairをA_i<B_iへswapしてからeventを置く。right event時にstackが空になる入力は端点distinctな正規pairでは起きないが安全に分岐できる。
復習の核
- disjoint、完全nested、端点が交互の二本、外側chordを跨いで複数交差する例でstack列を確認する。
計算量と制約
時間
O(N)。全2N端点のstack走査。
空間
O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2\leq N \leq 2\times 10^5; 1\leq A_i,B_i \leq 2N; A_1,\dots,A_N,B_1,\dots,B_N are all distinct; All input values are integers
出典