問題一覧 > 通常問題

No.2292 Interval Union Find

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

問題文

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

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

入力

$N\ Q$
${\rm Query}_{1}$
${\rm Query}_{2}$
${\rm Query}_{3}$
$\ \ \ \ \vdots$
${\rm Query}_{i}$
$\ \ \ \ \vdots$
${\rm Query}_{Q}$

  • ${\rm Query}_{i}$について
    タイプ1またはタイプ2のクエリのとき
    ${\rm type}_{i}\ L_{i}\ R_{i}$
    タイプ3のクエリのとき
    ${\rm type}_{i}\ u_{i}\ v_{i}$
    タイプ4のクエリのとき
    ${\rm type}_{i}\ v_{i}$
  • $2 \leq N \leq 10^{9}$
  • $1 \leq Q \leq 2 \times 10^{5}$
  • $1 \leq {\rm type}_{i} \leq 4$
  • $1 \leq L_{i} < R_{i}\leq N$
  • $1 \leq u_{i}, v_{i}\leq N$
  • 入力はすべて整数

出力

タイプ3、タイプ4のクエリが合計で $K$ 個与えられるとして、 $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:頂点 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。