ABC338 E - Chords

atcoder.jp

問題

• 時計回りに1から2Nまで並んだ2N個の頂点があるよ
• $A_i$と$B_i$が弦で繋がってるよ
• 弦は交差してる？

成約

• $2\leq N\leq 2\times 10^5$
• $A_i,B_j$はすべて相違なる

思考

• セグ木がうまく扱えたら、どうにかなった…かなぁ
• 成約より、各頂点に結ばれた弦は1本のみ
  • 頂点で交わることはない
• それぞれの弦を見ていきたい
• こういう時は円をどこか1点（大体1と2Nの間）で円を切って、直線で見てあげると良い典型らしい
  • 円を切って直線で見ると、括弧列問題に帰着できるっぽい
    • すべての括弧がユニークな括弧列判定！
  • 1~2Nまでの直線として見た時に、
    • 1から2Nまで順に頂点を見ていく
    • iから出てる弦の先をjとした時に、
      • iより大きい数字に繋がってるなら、stackに追加
      • iより小さい数字に繋がってるなら、stack末尾を確認
        • stack末尾=jなら、stackからpopして次に
        • stack末尾!=jなら、交点！
    • 全部見た時に交点が無いなら、交点無し！

コード

N = int(input())

edge_L = [0]*(2*N)

for i in range(N):
    A,B = map(int,input().split())
    edge_L[A-1] = B-1
    edge_L[B-1] = A-1

stack = []
for i in range(2*N):
    if edge_L[i] > i:
        stack.append(i)
    elif len(stack) and edge_L[i] == stack.pop():
        continue
    else:
        print('Yes')
        exit()

print('No')