【题目大意】给定一个长度为N的没有相同元素的序列，然后让你求一个连续子串A[I],A[I+1]….A[J]使得A[I]是这短子串中的最小值，A[J]是这段子串中的最大值，并使得它J-I的值最大。
【算法分析】我先假设确定了起点，然后考虑在O(lgN)的复杂度里找到对应的最长长度。对于这个问题，我们可以考虑先找出以I为起点的区间范围，即以A[I]为最小值的区间范围。找出这个范围以后，只需要再找出其中的最大值所在的位置，就已经找出了以I为起点对应的最长区间了。（因为这个数在可取值的范围里最大，所以不能再延伸区间了）。对于实现这个算法，我们很容易得到确定了起点的最小值单调递减，于是我们可以二分得到这个范围，复杂度O(lgN)。然后那个取最大值和最小值均可以用RMQ在O(1)的复杂度内搞出来。由于预处理RMQ复杂度也为O(NlgN)，所以整个算法的复杂度是O(NlgN)。
【其它】1A，今天的第10题，刷完睡觉
6430690 edward2 2452 Accepted 12516K 766MS G++ 1971B 2010-02-10 01:08:32
【CODE】
#include