Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 298 C問題 Cards Query Problem

AtCoder ABC ABC298 C問題 300 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

1 から N までの番号がついている N 個の空の箱と何も書かれていないカードが無数になる.

次の Q 個のクエリを順に処理せよ.

  • Type 1: 新たに i と書かれたカードを用意し, 箱 j に入れる.
  • Type 2: 箱 i に入っているカードに書かれた数を昇順で全て答える
  • Type 3: i と書かれたカードが入っている箱を昇順で全て答える.

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • Type 1
    • 1 \leq i \leq 2 \times 10^5
    • 1 \leq j \leq N
  • Type 2
    • 1 \leq i \leq N
    • 箱 i にはカードが 1 枚以上入っている.
  • Type 3
    • 1 \leq i \leq 2 \times 10^5
    • i と書かれたカードが入っている箱が存在する.
  • 出力すべき整数の数は 2 \times 10^5 個以下である.

解法

次の 2 つのデータ構造を用意する.

  • i=1,2, \dots, N に対して, 多重集合 (またはリスト) {\rm Box}_i を箱 i が入っているカード全体の集合 (リスト) とする.
  • i=1,2, \dots, 2 \times 10^5 に対して, 集合 {\rm Card}_i を i と書かれたカードが入っている箱全体の集合とする.

このとき, 次のように処理すれば良い.

  • Type 1: {\rm Box}_j に i を追加し, {\rm Card}_i に j を追加する.
  • Type 2: {\rm Box}_i の要素を昇順ソートし, 出力する.
  • Type 3: {\rm Card}_i の要素を昇順にソートし, 出力する.

計算量は出力する整数の数を K とすると, O(K \log K) 時間である.