Codeforces Round #333 (Div. 2) D. Lipshitz Sequence
問題文
考察
離散的な関数$f$に対して、以下のような定理が成り立つ。
この定理の系として以下のものが導ける。
この定理より、$L=\max |f'(x)|$であることが分かる。
なお、この定理は実際にグラフ書いてみれば成り立つことが確認できる。
平均値の定理と考えてもいいかも。
解法
考察の結果、$L(h[l..r])=\max |h'|[l..r)$であることがわかった。というわけで、区間$[l,r]$のクエリ結果は以下の式で求まる。 $$\sum_{l \le i \lt j \le r} \max |h'|[i..j)$$
この計算を高速に行おう。スタックの中に$L=p$であるようなものが$q$個あるという情報を積んでいくと、高速にいける。
たとえば$|h'|=[6,4,3,5,2,7]$だったとして、動作をシミュレートしてみる。
まず(6,1)をスタックに入れる。これは$[?..1]$の形の区間の中に、$L=6$であるものが1個あることを意味する。
次に(4,1)をスタックに入れる。これは$[?..2]$の形の区間の中に、$L=4$のものが1個、$L=6$のものが1個あることを意味する。
次に(3,1)をスタックに入れる。これは$[?..3]$の形の区間の中に、$L=3$のものが1個、$L=4$のものが1個、$L=6$のものが1個あることを意味する。
次に5を追加する。このときスタックは図のように更新される。これは$L=5$のものが3個、$L=6$であるものが1個あることを意味する。$L=3,4$であるようなものは、5を後ろにくっつけたことにより$L=5$に変化した。
あとは同様に操作を行っていく。
さて、肝心な計算量を解析しよう。スタックのpush回数とpop回数がわかれば計算量もわかる。push回数はn回である。pop回数は、ある要素が2回以上popされないことを考えると、たかだかn回だとわかる(追記 2015-11-27: n回しかpushしないのだからn回以上popできるわけがないと考えた方が分かりやすいかも)。つまり計算量は$O(n)$である。クエリ数を$Q$とすれば全体の計算量は$O(nQ)$になる。
Codeforces Round #333 (Div. 2) D. Lipshitz Sequenc ...
感想
スタック解法頭いい。