JOI 難易度11全部埋める #9 火事 (Fire) (2020本選)

明けましておめでとうございます、で新年一発目にやる問題の題材としては縁起悪いけど

最適化とかではなく、いいデータ構造を作って区間クエリに答える問題。 $S_{t, i} = \max(S_{t-1, i-1}, S_{t-1, i})$ 、 $S_{0, i} = A_i$ という漸化式で定められる配列において、 $t,l,r$ が与えられるので $\sum_{i=l}^r S_{t, i}$ を答えるクエリにたくさん答える。

ロボ「 $t=0$ に全部の家を消化すればいいのに……」

考察1

まず、 $S_{t, i} = \max_{\max(0, i - t) \le x \le i} A_x$ である。そして、最終形としては累積maxのようになる。なにか良い性質を見つけて良いデータ構造を作らないと。

おそらく対処すべき最も恐ろしいケースが $A_i = N-i$ である。

このケースは種類数が全然減らないし、各項における更新回数もほとんど $O(N)$ である。ただし、ほとんどの要素は shift しているので、両端キューで解決できる形である。しかしこれが他のものと複合になった場合、どのように扱えばいいか、どのように計算量を削減するかは問題である。一種の考えられるオチとしては、「何回か行うとそのような複雑性が減って簡単になる」というものである。

考察2

最終的に左の強いものに飲まれる。右の弱いものは自分が飲み込む。こういう構造を見ると、結構 Cartesian Tree と相性がよいと思える。

うーん？？？見える性質はあるが、特に $t$ に対して何か明らかにわかることがあるかと言われればよくわからない。むしろ、累積 max の更新点を子に持つというグラフのほうが性質をよく表していそう。

これはいいグラフだが、やはり $t$ に対して何かいうには物足りない。むしろ、何回か行ってこのグラフにもう少し特異な性質をもたせる必要があると思えてきた。

いま、「 $B$ 回行う」というのは、それぞれについて更新・累積和を $O(N)$ 計算すればクエリは $O(1)$ で処理できるため合計 $O(NB+Q)$ 時間で行える。処理も軽いし、 $B \le \sqrt{N}$ でも余裕だろう。問題なのはこの後である。なかなか見えてこない。

考察3

各 $A_i$ の運命は、「左の壁」と「右の壁」と「長さの上限」があり、途中は shift されるようになっている。式で書くと, $[\max(i, L_i + t), \min(i+1+t, R_i))$ が $A_i$ の支配するテリトリーである。

この壁があるのはいい性質だが、 $R_i$ はものによってはバラバラであり使うのは難しい。しかしいい形をしている。

考察4

$B$ 回処理後、細かい部分は排除されて結構滑らかになっていると思う。どういう意味で滑らかになっているのかはあまり言語化できない。「 $B$ ごとにブロックを分けるとブロック内の値の集合が2個しか更新されない」という予想を立てた。

これはかなり正しそうに見える。正確にいうと、「左からやってくる値が挿入され、最も小さい値が排除される」というものである。その後、順序を保ったまま（同じ値は index は大きいものが順序が小さいとして）値が shift されるようになっている…… と思っていたのだが、実際は少し駄目らしい（というのが後でわかった）。5 4 3 5 5 みたいなブロックに 9 を挿入していくと、5 4 3 5 5 → 9 5 4 5 5 → 9 9 5 5 5 → 9 9 9 5 5 → 9 9 9 9 5 → 9 9 9 9 9 となるが、順序にはいまいち沿っておらず駄目である。結構最後までなぜか勘違いしていてOKだと思ってしまった。

B を平方分割して、B回までは $O(NB)$ だった。 B 回以降も合計 $O(NB)$ で処理したいところである。「1時間ごとにブロックの左からやってくる侵略者たち」はどんどん値が大きくなるので、それを使えばshift は侵略者の両端キューで表現できる。1時間経つごとに

両端キューの左に侵略者が追加される (変更1)
両端キューの最右と在来の値を比較して、在来の方が強かったら侵略者は負けて両端キューの後ろが削られる。そうでなかったら、侵略者がそのまま侵略する (変更 2)

となって変更はちょうど2回となる。つまり、これは「ブロックごとに値の集合として管理できる」という構造になっている。実際は左からやってくる侵略者の値がどれかを求めないといけないため情報が足りないが、これは結構すごい性質！ネタバレになるが、「難易度11全部埋める #6」でも同じような性質が出てくる。

考察5

この間に実装してWAが出たりローカルで 4 秒（ジャッジは 1 秒）で困っていたりしたのだが、最終的に次のように平方分割した：

最初から B 個ごとにブロックを分ける。B時間後、左から侵略者がこない場合にブロック内は完結する：「3 1 4 5 1 / 2 1 5 9 3」の場合、「3 3 4 5 5 / 2 2 5 9 9」となる。その後、B時間分の侵略者を両端キューで計算する：「2 2 5 9 9」のブロックには「1, 5, 5, 5, 5」が順にやってくる。その後は N-B 回分頑張る。

値は vector と両端キューの min になっているため、各点取得は簡単。総和はブロックごとに管理しているため、区間和クエリはいつもの平方分割で $O(N/B)$ 時間。 $B = \sqrt{N}$ とすれば $O((N+Q) \sqrt{N})$ 時間となる。実行時間制限が 1.5 sec なのはかなり厳しく、さらに両端キューを使っているのでどうかと思ったが、なんとか通った。