decremental neighbor query とは
これ
長さ $N$ の bit 列があり、最初はすべての bit が立っています。次の $2$ 種類のクエリをたくさん処理してください。
- bit $a$ を下ろす。
- $b\lt x$ であって、 bit $x$ が立っているような最小の $x$ を求める。
問題
yukicoder No.2162 Copy and Paste 2
解法
とりあえず
$k=1,2,\ldots ,|S|$ の順に、次のテーブルを計算します。
- $U$ の長さを $k$ 以下に制限したときに、 $T$ を $S$ の先頭 $l$ 文字に一致させるのに必要な操作回数 $A_{k,l}$
計算するときは、まず $k$ 文字を $U$ にコピーし、貪欲にペーストしながら $T$ を構築することをシミュレーションします。
このままでは更新回数が多くなってしまうかもしれませんが、 A, B キーの性質を利用して
$$A_{k,l}=\min_{j=0}^l \left\lparen {B_{k,j}+(l-j)}\right\rparen$$
を満たす $B_{k,l}$ を計算することにすれば、更新回数が $O(|S|\log |S|)$ で抑えられます。なぜなら、シミュレーションに現れるペーストの回数は調和級数の性質より $O(|S|\log |S|)$ で、ペーストした直後のみ $B$ を更新すればよいからです。
結局、 $U$ が $S$ の先頭 $k$ 文字であるときの貪欲なペーストのシミュレーションを高速化することが焦点になります。
ここで DNQ の出番
ペースト可能な場所というのは、 $S$ の連続した部分のうち $S$ の先頭 $k$ 文字と一致するようなところですから、 $k$ が増加するとペースト可能な場所は単調に減少します。また、シミュレーションに必要な情報は、ある位置よりも右にあってペースト可能な場所のうち、最も左にあるような位置です。
これはまさしく、えびちゃんの日記で紹介されている decremental neighbor query に相当します。
decremental neighbor query は償却計算量で構築 $O(N)$ クエリ $O(1)$ で処理できるので、シミュレーションはペーストの回数に比例する時間計算量で実行でき、よって全体の計算量は $O(|S|\log |S|)$ になります。
やったね
実装例