AtCoder Beginner Contest 260 D問題 Draw Your Cards

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$1$ から $N$ までの整数が書かれたカードが1枚ずつ計 $N$ 枚あり, 裏向きで1つの山に積まれている. 上から $i$ 番目のカードに書かれているカードは $P_i$ である.

次の操作を $N$ 回行う.

山札の一番上のカードを引き, 表向きにする. このカードにかかれている整数を $X$ とする.
場に見えているカードのうち, $X$ 以上のカードが存在すれば, $X$ 以上の最小の整数が書かれているカードの上にそのカードを重ねる. もし, 存在しなければ, どのカードにも重ねずに置く.
その後, 表向きのカードが $K$ 枚重なった山があれば, その山にあるカードを全て食べる.

それぞれのカードについて, 食べられることはあるか? あるならば, それはいつか?

制約

$1 \leq K \leq N \leq 2 \times 10^5$
$(P_1, \dots, P_N)$ は $(1,2, \dots, N)$ の並び替え.

解法

次の操作が高速にできるデータ構造 $O$ を利用する必要がある.

$O$ に要素 $x$ を追加/削除する.
$O$ にある $x$ 以上の整数で最小の要素を見つける.

このデータ構造 $O$ としては, 例えば, 順序付き集合や BIT 木を利用することにより可能にする. 以下, $O$ はそのようなデータ構造とする.

表向きに見えているカードを記録するデータ構造として $O$ を利用する. また, $k$ と書かれた整数があるカードがある山にある一番下にあるカードに書かれている整数を表す変数を ${\rm id}_1, \dots, {\rm id}_N$ とし, ${\rm id}_i=k$ を満たすような整数 $i$ のリストを ${\rm deck}_k$ で表すとする.

の順に以下を処理する.
- $O$ に $P_i$ 以上の要素が存在する場合, $O$ にある $P_i$ 以上の最小の要素を $q$ とし, $O$ から $q$ を削除する. その後, ${\rm id}_{P_i} \gets q$ とする.
- $O$ に $P_i$ 以上の要素が存在しない場合, ${\rm id}_{P_i} \gets P_i$ とする.
- ${\rm deck}_{{\rm id}_{P_i}}$ に $P_i$ を追加する.
- ${\rm deck}_{{\rm id}_{P_i}}$ の長さが $K$ であるとき, $O$ から $P_i$ を削除し, ${\rm deck}_{{\rm id}_{P_i}}$ の各項に答えが $i$ であることを記録する.