[Q] https://atcoder.jp/contests/abc238/tasks/abc238_e

A. UnionFindすれば、すぐのようだ。

N=3 Q=3
1 2 をuniteして
2 3 をuniteして
2 2 をuniteして、

1 と 3 が同じ集団ならYes。

そんな優れた解法は思いつかないので、無様に吐き出し法で解く。

1. {R, L} で降順sortする。Rの大きい値から処理する。

2. Rが同じ値の組み合わせについて。{ {5, 3}, {5, 2}, {5, 1} } の3本。
a) 1本目は基底として採用。{5,3} が基底。これで5-3まで網羅。
b) 2本目以降は、前Lで切断する。前L=3
{5, 2}は、切断して{3, 2}として扱う。前L=2
{5, 1}は、切断して{2, 1}として扱う。前L=1

3. 上位の基底から採用した場合、N~0までつながるならYes。

N=5 Q=4
5 5
5 4
5 3
5 2

1. ｛R, L-1} に降順ソートする。
5 4
5 3
5 2
5 1

2. R=5で走査。
a) 1本目
5 4 は基底として採用。前L=4

b) 2本目
5 3 は {4 3} に切断。// {前L 今L}

c) 3本目
5 2 は{3 2} に切断。

d) 4本目
5 1 は{2 1} に切断。

今時点で、以下の4本として扱う。
5 4 <= 基底
4 3
3 2
2 1

・R=4
4 3 だけなので基底。

・R=3
3 2 だけなので基底。

・R=2
2 1 だけなので基底。

3. 基底をつなげる。
5 4 
4 3
3 2
2 1

ときれいにつながるが、5-0まで網羅できないのでNo。//L-1しているので、Lは0までつながりたい。

実装

priority_queue<ll> P[200010];
int main() {
 cincout();

 ll N, Q;
 cin >> N >> Q;
 rep(i, Q) {
   ll l, r;
   cin >> l >> r;
   --l;
   P[r].push(l);
 }
 vector<pll> E;  // 基底リスト
 E.reserve(N);
 ll now = N;
 while (now > 0) {
   ll nx = now;
   while (!P[now].empty()) {
     auto q = P[now].top();
     P[now].pop();
     if (nx == now) {  // 1本目なら既定にする
       E.push_back({now, q});
     } else {  // 2本目以降は切断して、P[前L]に辺追加
       P[nx].push(q);
     }
     nx = q;
   }
   --now;
 }
 bool ok = true;
 now = N;
 for (auto e : E) {  // 既定の上位から採用。N~0までつながるか
   ll r = e.first;
   ll l = e.second;
   if (r > now)
     continue;
   else if (r == now)
     now = l;           // nowをL に更新
   else if (r < now) {  // now=3 r=2なら、3をとる基底がないのでNG
     ok = false;
     break;
   }
 }
 if (now > 0) ok = false;
 if (ok)
   cout << "Yes" << endl;
 else
   cout << "No" << endl;
}

https://atcoder.jp/contests/abc238/submissions/29098337