Codeforces Round #333 (Div. 2) D. Lipshitz Sequence

問題文

codeforces.com

考察

離散的な関数$f$に対して、以下のような定理が成り立つ。

$$f'(x) \le \frac{f(b)-f(a)}{b-a} \le f'(y)$$ を満たす整数$a\le x,y \lt b$が存在する。ただし$f'(x)=f(x+1)-f(x)$とする。

この定理の系として以下のものが導ける。

$$ \left| \frac{f(b)-f(a)}{b-a} \right| \le |f'(x)|$$ を満たす整数$a\le x \lt b$が存在する。

この定理より、$L=\max |f'(x)|$であることが分かる。

なお、この定理は実際にグラフ書いてみれば成り立つことが確認できる。

f:id:pekempey:20151125171126p:plain:w300

平均値の定理と考えてもいいかも。

解法

考察の結果、$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個あることを意味する。

f:id:pekempey:20151125181912p:plain:w350

次に(4,1)をスタックに入れる。これは$[?..2]$の形の区間の中に、$L=4$のものが1個、$L=6$のものが1個あることを意味する。

f:id:pekempey:20151125181915p:plain:w350

次に(3,1)をスタックに入れる。これは$[?..3]$の形の区間の中に、$L=3$のものが1個、$L=4$のものが1個、$L=6$のものが1個あることを意味する。

f:id:pekempey:20151125181918p:plain:w350

次に5を追加する。このときスタックは図のように更新される。これは$L=5$のものが3個、$L=6$であるものが1個あることを意味する。$L=3,4$であるようなものは、5を後ろにくっつけたことにより$L=5$に変化した。

f:id:pekempey:20151125181921p:plain:w400

あとは同様に操作を行っていく。

f:id:pekempey:20151125181924p:plain:w400
f:id:pekempey:20151125184546p:plain:w400

さて、肝心な計算量を解析しよう。スタックの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 ...

感想

スタック解法頭いい。