いうほどUnion-Find使わなかったな…。
https://yukicoder.me/problems/no/2292
問題
1~Nのラベルを持つN頂点の無向グラフを考える。初期状態で辺はない。
以下のクエリに順次答えよ。
- 区間[L,R]が指定されるので、その区間に対応するラベルを持つ全頂点間に辺を追加する
- 区間[L,R]が指定されるので、1≦u<R、L<v≦Nとなる点(u,v)間の辺を削除する
- 2点が指定されるので、連結か判定する
- 1点が指定されるので、その点が含まれる連結成分のサイズを答える
解法
この手順で連結となるのは、ある連続したラベルの区間のみとなる。
そこで、以下ではsetを使いサイズ2以上の連結成分について区間の集合を管理した。
int N,Q; set<pair<int,int>> S={{-2,-1},{1<<30,1+(1<<30)}}; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; while(Q--) { cin>>i; /* FORR2(a,b,S) cout<<a<<":"<<b<<" "; cout<<endl; */ if(i==1||i==2) { int L,R; cin>>L>>R; if(i==1) { pair<int,int> P={L,R}; auto it=S.lower_bound({L+1,0}); it--; if(it->second>=L) { P.first=it->first; P.second=max(it->second,R); S.erase(it); } while(1) { it=S.lower_bound({L+1,0}); if(it->first<=R) { P.second=max(P.second,it->second); S.erase(it); } else { break; } } S.insert(P); } else { while(1) { auto it=S.lower_bound({L,0}); if(it->first>=R) break; if(it->second<=R) { S.erase(it); } else { auto p=*it; S.erase(it); S.insert({R,p.second}); } } while(1) { auto it=S.lower_bound({R,0}); it--; if(it->second>R) { auto p=*it; S.erase(it); S.insert({p.first,L}); S.insert({R,p.second}); } else if(it->second>L) { auto p=*it; S.erase(it); S.insert({p.first,L}); } break; } } } else if(i==3) { cin>>x>>y; if(x>y) swap(x,y); auto it=S.lower_bound({x+1,0}); it--; if(x==y||it->first<=x&&y<=it->second) { cout<<1<<endl; } else { cout<<0<<endl; } } else { cin>>x; auto it=S.lower_bound({x+1,0}); it--; if(it->first<=x&&x<=it->second) { cout<<1+it->second-it->first<<endl; } else { cout<<1<<endl; } } } }
まとめ
区間を追加したり削除したりするの、いい加減ライブラリ化しようかな…。