山の「次の山」は、かつであるような最小のである。(→ next greater element) 各山に向かって次の山から辺を張ったグラフは有向森であり、この森にに対応する大頂点を加えると頂点を根とする有向木(out-tree)になる。この木をとする。この時、クエリはの一部を切り取ったグラフの最も長いパスの頂点数を質問していることになる。
- クエリを処理する時、をより小さくしても得しないので、を固定してについて最大値が求まればよい。これは適当な列が得られていればRMQに帰着するはずだが、どうやってその列を得るかが問題となる。
- 任意のについて、をの時の求める値、と定める。このとき、は上のの部分木に含まれる各位置に+1したものになっている。
- の頂点番号はの帰りがけ順についているので、部分木への加算はのある区間への加算になっている。
したがって、クエリ先読みができるならを区間max・区間addの遅延セグメント木で持っての昇順に更新しつつ、各に対応するクエリをまとめて処理すればよい。満点を取るにはオンラインで処理する必要があるが、これは永続化でできる。
この問題の場合はStarry Sky treeでいいので、普通の永続セグメント木と同じように素朴なpath copyingでできる。
わからなかった。上の方針はEditorialの方針とanubhavdharさんの書き込みのハイブリッドみたいなやつ。
