2300diffにしては難しくないか? けっこう苦労したのでメモ。
数列 $A=(A_1,A_2,...,A_N)$ に対して以下の操作を $0$ 度以上何度か行うことを考える。
$i=A_i$ なる整数 $i$ を選び、 $A_i$ を数列から消す。空いた添え字は詰められる。( $(A_1,A_2,A_4,A_5,\dots)$ のような添え字の付け方にはならない)
以下の $Q$ 個のクエリに答えよ。
与えられる数列 $A$ の先頭 $X$ 個、末尾 $Y$ 個の要素を $n+1$ (つまり、削除不能な要素)に置換した数列 $B$ を考える。この $B$ に対してうまく操作をしたとき、最大で何度操作できるか答えよ。
$1 \le N,Q \le 3 \times 10^5$
ひとまず、「ある要素 $A_x$ について、ある区間を指定した時にその範囲内で消せるか?」という問題を解きたい。
ここで、 $A_x$ より後ろの要素については $A_x$ が消せるかどうかには絡んでこない。なので、この判定を行う時に着目すべきは $A_x$ より前である。
まず、 $A_x=x$ の場合は明らかに消せて、 $x<A_x$ の場合は消しようがない。問題は $A_x<x$ の場合。この時、 $A_x$ より前で $x-A_x$ 個の要素が消えることが必要となる。
少し検討すると、以下が必要十分であることが分かる。
$A_x$ より前にある要素であり、 $y-A_y<x-A_x$ なる要素のうち最も右のものを $A_y$ とする。
$A_y$ より前にある要素であり、 $z-A_z<x-A_x-1$ なる要素のうち最も右のものを $A_z$ とする。
$A_z$ より前にある要素であり、 $w-A_w<x-A_x-2$ なる要素のうち最も右のものを $A_w$ とする。
…
これを繰り返し、 $A_p=p$ なる要素 $p$ に辿りつければ $A_x$ は消せることとなる。
これが分かると当たり前なのだが、要素 $A_x$ に対して、それが $(A_i,A_{i+1}\dots,A_x)$ の範囲内で消せるならば、この範囲の左端がさらに左にあってもその範囲内で消せる。
なので、ある要素からどんどん左へと左端を伸ばしていき、その範囲内だけでその要素を消せるようになる境界の点を求めれば、数列を右から左へと見ていくようにするとうまくクエリにオフラインで対応できそうだ。
なので、左端のうち最も右のものをまとめて求めることを考えるが、ここでも数列を右から左へと見ることを考える。このとき数列の左端にある値が追加されて何が起こるかを考えればうまくいく。
もし $x<A_x$ なる要素が左端に追加されたら、これはただの置物なので何もしなくてよい。
もし $x=A_x$ なる要素が左端に追加されたら、その要素自身の左端のうち最も右のものをその要素自身に設定する。さらに、「あとひとり消せるものが前にあれば、それ自身も消せる」というものの左端のうち最も右のものもこの要素になる。さらに、それ以降のものについても必要十分条件で述べた遡りが一段進む。
もし $x>A_x$ なる要素が左端に追加されたら、この差分より真に大きいものに対して遡りが一段進む。
普通にやると $O(N^2)$ かかりますが、配列を横に並べたようなデータ構造で、任意ヶ所で隣接要素をマージしたり高速に $k$ 番目にアクセス出来るようにしたりを高速でするようにする(頑張る)と $O(N \log N)$ で全ての要素について求めたい左端が出てくるので、あとは配列を右から左へ見つつRSQでごりごりやるとこの問題に正解できます。
すごい言語化が下手なので、コード見てもらった方が早いと思います…
Submission #146179508 - Codeforces
