問題一覧 >
通常問題
No.2292 Interval Union Find
レベル :
/ 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ :
/
解いたユーザー数 47
作問者 :
t98slider
/ テスター :
hikikomori
問題文最終更新日: 2023-05-11 02:55:52
問題文
N 頂点 0 辺の無向グラフがあります。頂点にはそれぞれ 1 から N までの番号が付けられています。
以下のような Q 個のクエリが与えられるので順に処理してください。
1 L R
:L≤u<v≤R を満たす頂点対 (u,v) についてすべて辺で結ぶ。
2 L R
:1≤u<R 、L<v≤N を満たす頂点対 (u,v) を端点とする辺をすべて削除する。
3 u v
:頂点 u と頂点 v が連結であるかを判定する。連結であれば1
、連結でなければ0
を出力する。
4 v
:頂点 v が属する連結成分に含まれる頂点の個数を出力する。
入力
N Q
Query1
Query2
Query3
⋮
Queryi
⋮
QueryQ
- Queryiについて
タイプ1またはタイプ2のクエリのとき
typei Li Ri
タイプ3のクエリのとき
typei ui vi
タイプ4のクエリのとき
typei vi
- 2≤N≤109
- 1≤Q≤2×105
- 1≤typei≤4
- 1≤Li<Ri≤N
- 1≤ui,vi≤N
- 入力はすべて整数
出力
タイプ3、タイプ4のクエリが合計で K 個与えられるとして、 i (1≤i≤K) 行目にそれぞれのクエリの回答を1行に出力してください。
サンプル
サンプル1
入力
10 18
4 3
1 1 2
4 1
1 2 3
3 1 3
1 6 7
1 8 9
3 7 8
1 7 10
3 6 10
1 7 9
4 10
1 2 8
4 5
2 2 6
4 2
4 5
4 6
出力
1
2
1
0
1
5
10
2
1
5
サンプル1の説明を見る (クリックで展開します)
タイプ1、タイプ2のクエリに相当する区間は以下のようになっています。(黒:タイプ1、赤:タイプ2)
4 3
:頂点 3 と連結である頂点は1つなので 1
を出力します。
1 1 2
:頂点対 (1,2) について辺で結びます。
4 1
:頂点 1 と連結である頂点は2つなので 2
を出力します。(頂点 1 , 2)
1 2 3
:頂点対 (2,3) について辺で結びます。
3 1 3
: 頂点 1 と頂点 3 は連結なため 1
を出力します。
1 6 7
:頂点対 (6,7) について辺で結びます。
1 8 9
:頂点対 (8,9) について辺で結びます。
3 7 8
: 頂点 7 と頂点 8 は連結ではないなため 0
を出力します。
1 7 10
:頂点対 (7,8),(7,9),(7,10),(8,9),(8,10),(9,10) について辺で結びます。
3 6 10
:頂点 6 と頂点 10 は連結なため 1
を出力します。
1 7 9
:頂点対 (7,8),(7,9),(8,9) について辺で結びます。
4 10
:頂点 10 と連結である頂点は5つなので 5
を出力します。(頂点 6,7,8,9,10)
1 2 8
:以下の頂点対について辺で結びます。
(2,3),(2,4),(2,5),(2,6),(2,7),(2,8)
(3,4),(3,5),(3,6),(3,7),(3,8)
(4,5),(4,6),(4,7),(4,8)
(5,6),(5,7),(5,8)
(6,7),(6,8)
(7,8)
4 5
:頂点 5 と連結である頂点は10個なので 10
を出力します。(頂点 1 ~ 10)
2 2 6
:以下の頂点対について存在する辺を削除します。((u,v)=(v,u) の重複や同一頂点を省いています。)
(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10)
(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(2,10)
(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),(3,10)
(4,5),(4,6),(4,7),(4,8),(4,9),(4,10)
(5,6),(5,7),(5,8),(5,9),(5,10)
4 2
:頂点 2 と連結である頂点は2つなので 2
を出力します。(頂点 1 , 2)
4 5
:頂点 5 と連結である頂点は1つなので 1
を出力します。
4 6
:頂点 6 と連結である頂点は5つなので 5
を出力します。(頂点 6,7,8,9,10)
サンプル2
入力
10 11
1 1 3
1 4 6
1 7 10
4 5
1 2 8
4 5
2 4 5
4 4
4 5
3 10 7
3 10 4
出力
3
10
4
6
1
0
サンプル3
入力
998244353 7
1 3 998244353
4 998244353
2 2 50
4 998244353
2 2023 20232023
4 2000
4 998244353
出力
998244351
998244304
1974
978012331
サンプル4
入力
2 9
3 1 1
3 2 2
1 1 2
3 1 1
3 2 2
3 1 2
2 1 2
3 1 1
3 2 2
出力
1
1
1
1
1
1
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。