POJ 2452 RMQ+二分
解法是
枚举每个位置i，找出i右边比第一个比a[i]小的a[j]的位置j
在i到j - 1中间求最大值的位置k 如果a[k] > a[i] 那么更新答案
#include <iostream>#include <algorithm>#include <cstring>#include <string>#include <cstdio>#include <cmath>#include <queue>#include <map>#include <set>#define eps 1e-5#define MAXN 55555#define MAXM 111111#define INF 1000000000using namespace std;int mi[MAXN][17], mx[MAXN][17], w[MAXN];int Log[MAXN];int n;void rmqinit(int n){ for(int i = 1; i <= n; i++) mi[i][0] = mx[i][0] = i; int m = (int)(log(n * 1.0) / log(2.0)); for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) { mx[j][i] = mx[j][i - 1]; mi[j][i] = mi[j][i - 1]; if(j + (1 << (i - 1)) <= n) { if(w[mx[j][i]] < w[mx[j + (1 << (i - 1))][i - 1]]) mx[j][i] = mx[j + (1 << (i - 1))][i - 1]; if(w[mi[j][i]] > w[mi[j + (1 << (i - 1))][i - 1]]) mi[j][i] = mi[j + (1 << (i - 1))][i - 1]; } }}int rmqmin(int l,int r){ int m = Log[r - l + 1]; if(w[mi[l][m]] > w[mi[r - (1 << m) + 1][m]]) return mi[r - (1 << m) + 1][m]; else return mi[l][m];}int rmqmax(int l,int r){ int m = Log[r - l + 1]; if(w[mx[l][m]] < w[mx[r - (1 << m) + 1][m]]) return mx[r - (1 << m) + 1][m]; else return mx[l][m];}int bin(int x, int l, int r){ int ret = -1; while (l <= r) { int m = (l + r) >> 1; if (w[x] < w[rmqmin(l, m)]) l = m + 1, ret = max(ret, m); else r = m - 1; } return ret;}int main(){ Log[1] = 0; for(int i = 2; i < MAXN; i++) Log[i] = Log[i >> 1] + 1; while(scanf("%d", &n) != EOF) { for(int i = 1; i <= n; i++) scanf("%d", &w[i]); rmqinit(n); int ans = -1; for(int i = 1; i <= n; i++) { int r = bin(i, i + 1, n); int k = -1; if(r > i) k = rmqmax(i, r); if(w[k] > w[i]) ans = max(ans, k - i); } if(ans < 1) ans = -1; printf("%d\n", ans); } return 0;}