JOI2016 春合宿 - マトリョーシカ人形

• 問題
• AC

以下、入れ子になったマトリョーシカ人形のまとまりをパスと呼ぶ。ひとまずクエリのことは忘れて、直径と高さを限定しない場合のパスを数える。実際にパスを作りながら、配列$dp$に各パスのもっとも外側の直径を保持する。その際、$dp$は常に降順になるようにする。$dp$の長さは$N$あれば十分で、$0$に初期化しておく。

$dp$の更新は貪欲でよい。つまり、マトリョーシカ人形をあらかじめ高さの昇順（等しい場合は直径の降順）にソートしておけば、各マトリョーシカ人形$(d, h)$は$dp$の中で外側の直径が$d$未満かつ最大のものを選んで追加すれば良いはずである。¹ ステップごとに追加場所を二分探索すればいいので${\mathcal O}(N \log N)$で構築できる。最終的にパスが何個できているかは、$dp$の二分探索で直径$1$以上のパスを数えればわかる。

さて、実際にはクエリごとに直径$d'$以上、高さ$h'$以下に限った場合のパスを数えなければならない。上の構築をよく見ると、直径$d'$未満のマトリョーシカ人形を無いものとしても各マトリョーシカ人形を追加する場所は変わらない。したがって、制限を無視して構築した$dp$について、二分探索で（直径$1$以上の代わりに）直径$d'$以上のパスを数えれば良い。また、高さ$h'$以下に限るという条件については、オフラインクエリなのでクエリを高さの昇順でソートしておいて、$dp$を必要な高さまで構築しながら答えていけば良い。${\mathcal O}((N+Q)\log N)$。

考察は順調に進んだのだが、最後のステップになかなか気づけなかった。クエリを並べ替えるのは知識としてはあったけれど、実際にそれが必要な問題を解いたのは初めてだと思う。

あと、なぜか$dp$にBITを使って解いてしまった。翌日見直していてようやく、BITの機能を使っていないことに気づいた。

ところで、オンラインクエリだったらどうするんだろう。よく知らないけど永続配列とか使うしかないのかな。

---

1. 解いている時は明らかだと思ったけど非自明だった。あとで考えるかも。Dilworthの定理？ ↩︎