題目大意: 給定一個長度為n的序列，序列裡的元素都不相同，要求找出一對（i，j）,i<j,arr[k]>=i&arr[k]<=j，All(i < k < j).然後求最大的j-i差值。
解題思路：RMQ+二分，有人暴力過，估計是數據的問題。先初始化rmq，這裡的dp數組存儲的是序列的下標。然後枚舉每個結束點x，用rmq查詢離x點最遠的點j，使得max[j,x-1] < x，這裡要用到二分，查詢區間最值有rmq。找出最遠的那個點j後，就要找[j,x-1]區間內值最小的那個下標i，然後x -i就是以x結尾符合條件的最長序列。
為什麼可以二分？為什麼找出離x最遠的點再找區間內的最小值就是以x結尾的最長序列呢？
首先回答第一個問題，因為我們要找的是x-1以前的某個j使得max[j,x-1] < x,要找的是區間的最值，某個區間最值小於x，那麼它的子區間最值也小於x，這是顯然的。那找到了一個位置符合情況，就可以保證大於這個位置的都符合情況，也就自然可以往更前面查找。
現在來回答而第二個問題，前面已經找到那個最左邊的位置j了，現在要找值最小的那個i，找到了從[i,x]內的值都大等於i，小等於x，符合情況。如果不是最小的，那麼這個最小的就會跳出來大吼：你大子還不夠小，自然不是合法情況。
測試數據：
4
5 4 3 6
4
6 5 4 3
C艹代碼：
[cpp]
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX 51000
int n, m, ans, arr[MAX];
struct RMQ {
int mmin[MAX][20];
int mmax[MAX][20];
void Create();
int Query(int l, int r, int kind);
} rmq;
inline int min(int x,int y) {
return arr[x] < arr[y] ? x : y;
}
inline int max(int x,int y) {
return arr[x] > arr[y] ? x : y;
}
void RMQ::Create() {
int i, j = 2, k = 0;
for (i = 1; i <= n; ++i)
mmin[i][0] = mmax[i][0] = i;
while (j <= n) k++,j *= 2; //用這個而非log快了1000ms
for (j = 1; j <= k; ++j)
for (i = 1; i + (1 << j) - 1 <= n; ++i) {
mmin[i][j] = min(mmin[i][j - 1], mmin[i + (1 << (j - 1))][j - 1]);
mmax[i][j] = max(mmax[i][j - 1], mmax[i + (1 << (j - 1))][j - 1]);
}
}
int RMQ::Query(int l, int r, int kind) {
int i = r - l + 1, j = 2, k = 0;
while (j <= i) k++,j *= 2; //用這個而非log快了1000ms
if (kind == 0)
return min(mmin[l][k], mmin[r - (1 << k) + 1][k]);
else
return max(mmax[l][k], mmax[r - (1 << k) + 1][k]);
}
int Find(int x) {
int low = 1,high = x - 1;
int i,mid,k = -1;
while (low <= high) {
mid = low + (high - low) / 2;
i = rmq.Query(mid,x-1,1); //查詢mid至x-1最大的那個下標
if (arr[i] > arr[x]) low = mid + 1;
else k = mid,high = mid - 1;
}
if (k == -1) return x + 1;
i = rmq.Query(k,x-1,0); //如果允許有重復值，這裡應該二分查找最小的那個下標
return i;
}
int main()
{
int i, j, k;
while (scanf("%d", &n) != EOF) {
for (i = 1; i <= n; ++i)
scanf("%d", &arr[i]);
rmq.Create();
for (ans = -1,i = n; i >= 1; --i) {
k = i - Find(i);
if (k > ans) ans = k;
}
printf("%d\n", ans);
}
}
