Codeforces 6E

問題

整数列が与えられるので、最大値と最小値の差分がK以下になるように取ることができる最長の連続領域の長さを求め、それに該当する区間をすべて列挙せよ、という問題。

解答例

とにかく最初から順番にできるだけ長い領域を確保する。こうすると次に入れることができない値が出てくるので、それが大きすぎるなら、それからKを引いた値以上の値が連続する位置から始まっていたことにして継続し、それが小さすぎるなら、それにKを加えた値以下の値が連続する位置から始まっていたことにして継続する。開始位置の修正を行うには、バイナリサーチを行って、ある位置から現在の位置までの最大値・最小値を持つセグメントツリーでも事前に構築しておけば高速に求まる。