Segment Tree - Educational Codeforces Round 78 div2 d

#set #sweep line #dsu(disjoint set union) #区間 #segment

解法

intersectの条件
2つの線分の一部が被ってる
(一方が他方を完全に覆っていてはいけない)

一部が被ってる2線分を考える
始点が先の線分を x , 始点が後ろの線分を y とする
x の始点より後に y の始点があり,
xの終点より後に y の終点がある
また, y の始点は x の始点, 終点に挟まれてる

前から見て, x の始点が来たら x の終点をsetに入れる
x の終点が来て x の終点をsetから取り出す前に y の始点が来るか
そして, y の終点は x の終点の後でないといけない

コード

unionfind ver
https://codeforces.com/contest/1278/submission/67319721

    int n;
    cin >> n;
    
    vector<pii> a(n);
    rep(i, n) cin >> a[i].F >> a[i].S;
    
    vector<pii> evs;
    rep(i, n) {
        evs.eb(pii(a[i].F, i));
        evs.eb(pii(a[i].S, i)); // setから取り出すために必要
    }
    sort(all(evs));
    
    int cnt = 0;
    set<pii> cur;
    UnionFind uni(n);
    
    for (auto it : evs) { // すべての線分の始点を見る
        if (cnt >= n) break;
        // curに入ってるのは終点
        // この点が終点なら取り出し, とばす
        // 以降, この線分が見られることはない
        if (cur.count(it)) {
            cur.erase(it);
        } else {
            int i = it.S;
            int r = a[i].S; // その線分の終点
            
            for (auto jt : cur) {
　　　　  // 完全に覆われていてはいけない
                if (jt.F > r) break; 
                int j = jt.S;
                uni.connect(i, j);
                cnt++;
                if (cnt >= n) { 
                    cout << "NO" << endl; 
                    return 0; 
                }
            }
            cur.insert(pii(a[i].S, i)); // 終点を入れる
        }
    }
    
    cout << (uni.size() == 1 ? "YES" : "NO") << endl;