POJ 2452 RMQ+二分 - c++编程基础

解法是

枚举每个位置i，找出i右边比第一个比a[i]小的a[j]的位置j

在i到j - 1中间求最大值的位置k 如果a[k] > a[i] 那么更新答案

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-5
#define MAXN 55555
#define MAXM 111111
#define INF 1000000000
using 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;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-5
#define MAXN 55555
#define MAXM 111111
#define INF 1000000000
using 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;
}