問題一覧 > 通常問題

No.2292 Interval Union Find

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : t98slidert98slider / テスター : hikikomorihikikomori
0 ProblemId : 9177 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-11 02:55:52

問題文

NN 頂点 00 辺の無向グラフがあります。頂点にはそれぞれ 11 から NN までの番号が付けられています。
以下のような QQ 個のクエリが与えられるので順に処理してください。

  • 1 L RLu<vRL \leq u < v \leq R を満たす頂点対 (u,v)(u, v) についてすべて辺で結ぶ。
  • 2 L R1u<R1 \leq u < RL<vNL < v \leq N を満たす頂点対 (u,v)(u, v) を端点とする辺をすべて削除する。
  • 3 u v:頂点 uu と頂点 vv が連結であるかを判定する。連結であれば1、連結でなければ0を出力する。
  • 4 v:頂点 vv が属する連結成分に含まれる頂点の個数を出力する。

入力

N QN\ Q
Query1{\rm Query}_{1}
Query2{\rm Query}_{2}
Query3{\rm Query}_{3}
    \ \ \ \ \vdots
Queryi{\rm Query}_{i}
    \ \ \ \ \vdots
QueryQ{\rm Query}_{Q}

  • Queryi{\rm Query}_{i}について
    タイプ1またはタイプ2のクエリのとき
    typei Li Ri{\rm type}_{i}\ L_{i}\ R_{i}
    タイプ3のクエリのとき
    typei ui vi{\rm type}_{i}\ u_{i}\ v_{i}
    タイプ4のクエリのとき
    typei vi{\rm type}_{i}\ v_{i}
  • 2N1092 \leq N \leq 10^{9}
  • 1Q2×1051 \leq Q \leq 2 \times 10^{5}
  • 1typei41 \leq {\rm type}_{i} \leq 4
  • 1Li<RiN1 \leq L_{i} < R_{i}\leq N
  • 1ui,viN1 \leq u_{i}, v_{i}\leq N
  • 入力はすべて整数

出力

タイプ3、タイプ4のクエリが合計で KK 個与えられるとして、 i (1iK)i\ (1 \leq i \leq 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:頂点 33 と連結である頂点は1つなので 1 を出力します。
  • 1 1 2:頂点対 (1,2)(1, 2) について辺で結びます。
  • 4 1:頂点 11 と連結である頂点は2つなので 2 を出力します。(頂点 11 , 22)
  • 1 2 3:頂点対 (2,3)(2, 3) について辺で結びます。
  • 3 1 3: 頂点 11 と頂点 33 は連結なため 1 を出力します。
  • 1 6 7:頂点対 (6,7)(6, 7) について辺で結びます。
  • 1 8 9:頂点対 (8,9)(8, 9) について辺で結びます。
  • 3 7 8: 頂点 77 と頂点 88 は連結ではないなため 0 を出力します。
  • 1 7 10:頂点対 (7,8),(7,9),(7,10),(8,9),(8,10),(9,10)(7, 8), (7, 9), (7, 10), (8, 9), (8, 10), (9, 10) について辺で結びます。
  • 3 6 10:頂点 66 と頂点 1010 は連結なため 1 を出力します。
  • 1 7 9:頂点対 (7,8),(7,9),(8,9)(7, 8), (7, 9), (8, 9) について辺で結びます。
  • 4 10:頂点 1010 と連結である頂点は5つなので 5 を出力します。(頂点 6,7,8,9,106, 7, 8, 9, 10)
  • 1 2 8:以下の頂点対について辺で結びます。
    (2,3),(2,4),(2,5),(2,6),(2,7),(2,8)(2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8)
    (3,4),(3,5),(3,6),(3,7),(3,8)(3, 4), (3, 5), (3, 6), (3, 7), (3, 8)
    (4,5),(4,6),(4,7),(4,8)(4, 5), (4, 6), (4, 7), (4, 8)
    (5,6),(5,7),(5,8)(5, 6), (5, 7), (5, 8)
    (6,7),(6,8)(6, 7), (6, 8)
    (7,8)(7, 8)
  • 4 5:頂点 55 と連結である頂点は10個なので 10 を出力します。(頂点 111010)
  • 2 2 6:以下の頂点対について存在する辺を削除します。((u,v)=(v,u)(u, v) = (v, u) の重複や同一頂点を省いています。)
    (1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10)(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)(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)(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)(4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (4, 10)
    (5,6),(5,7),(5,8),(5,9),(5,10)(5, 6), (5, 7), (5, 8), (5, 9), (5, 10)
  • 4 2:頂点 22 と連結である頂点は2つなので 2 を出力します。(頂点 11 , 22)
  • 4 5:頂点 55 と連結である頂点は1つなので 1 を出力します。
  • 4 6:頂点 66 と連結である頂点は5つなので 5 を出力します。(頂点 6,7,8,9,106, 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もしくは右上の雲マークをクリックしてアカウントを作成してください。