Codeforces Global Round 7 E. Bombs

Problem - E - Codeforces

問題概要

$1$ から $n$ までの順列 $p_{1}, ..., p_{n}$ が与えられる。

爆弾が仕掛けられているインデックスの集合 $B$ を考える。 $B$ に対して以下のように計算される値を $f(B)$ と定義する。

$A$ を空集合とする。
の順に以下の操作を行う。
- 集合 $A$ に $p_{i}$ を追加する。その後 $i \in B$ ならば爆弾が発動し、 $A$ の中で最大の要素が除外される。
この操作が完了した後、 $A$ に含まれる最大の要素が $f(B)$ である。

$1$ から $n$ までの順列 $q_{1}, ..., q_{n}$ が与えられる。初期状態の $B$ を空集合として、 $i=1, ..., n$ について順番に以下を処理せよ。

現時点での $B$ について $f(B)$ を出力せよ。その後、 $B$ に $q_{i}$ を追加せよ。

制約

$2 \le n \le 300000$
$p_{1}, ..., p_{n}$ は順列
$q_{1}, ..., q_{n}$ は順列

解法

まず「答えはある値 $k$ より小さいか？」という判定問題を考えます。これはつまり、 $k, ..., n$ の全ての値が除外されるか？ということです。

この判定問題を解く際には、操作は以下のように単純化できます。

の順に以下を行う。
1. $p_{i}$ が $k$ 以上ならば、値のストックを $1$ 個増やす。
2. $i \in B$ であり、値のストックが $1$ 個以上ならば、値のストックを $1$ 個減らす。

つまり具体的にどの値が $A$ に追加され除外されたかを考えなくても良くなります。この操作の結果として値のストックが $0$ 個であれば、 $k, ..., n$ の全ての値が除外されたことになります。

ただし $B$ が変更されるたびにこの操作を毎回やっていては間に合わないので、もう少し扱いやすい形にしましょう。

キーとなる考え方は累積和です。 $k$ 以上の値が追加されることを $+1$ 、爆弾が発動することを $-1$ として、先頭から累積和を取ることを考えます。

f:id:betrue12:20200321144608p:plain

この累積和において、「最小値」と「最後の値」に注目します。最小値よりも最後の値が大きい場合、最小値を取る時点より後に発生した $+1$ であって、 $-1$ によって相殺されなかったものが存在する、ということになります。逆も然りで、最小値と最後の値が等しい場合は全ての $+1$ が $-1$ で相殺されています。

よってこれら2つの値を見るだけで、「答えはある値 $k$ より小さいか？」という判定問題が解けることになります。

そしてこの形にしてしまえば、 $B$ の要素や判定問題の $k$ の値が変わっても対応できます。 $B$ に $q_{i}$ が追加されたときには、その位置に $-1$ を追加すれば良いです。また $B$ に要素が追加されることで答えの値は単調減少するので、判定問題の $k$ も1つずつ減らしていくことになります。 $k$ を $k-1$ に変えた時に、 $p_{i} = k-1$ である位置に $+1$ を追加すれば良いです。