Codeforces #6 E Exposition

題意﹕給了長度為的數列，取一連續子序列使得其最大和最小元素相差最多為。問該長度最長為多少？並且輸出所有符合條件的連續子序列的長度起點和終點。

很經典的RMQ，可以用Sparse Table或線段樹完成。維護兩棵線段樹，一記區間的最大值，一記區間的最小值。有一個簡單的觀察。

觀察: 對於固定的，是一單調上升序列，是一單調下降序列。因此是一單調上升序列。

由此可以，枚舉，然後可以用二分法，二分長度，找出最長的長度使得。
最長長度則是。

在線段樹查詢區間是，而枚舉加二分長度，整個算法是。