POJ 2823 Sliding Window （RMQ + 滚动数组）
正常的ＲＭＱ询问区间的最大最小值问题，只是如果普通的开dp[i][j]的话，铁定超内存。
题目中给定了询问的区间长度k所以，只需要用一位数组存dp[i]表示i到i+k-1区间的最值
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 1000050
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;
int dp1[MAX],dp2[MAX],a[MAX]; // dp[i]表示i到i+k-1区间的最值
int n,m,k;
inline int min(int a,int b) {
return a < b ? a : b;
}
inline int max(int a,int b) {
return a < b ? b : a;
}
void initRMQ() {
for(int i=1; i<=n; i++) {
dp1[i] = a[i];
dp2[i] = a[i];
}
for(int j=1; j<=k; j++) {
for(int i=1; i<=n; i++) {
if(i + (1 << (j-1)) <= n) {
dp1[i] = min(dp1[i],dp1[i + (1 << (j-1))]);
dp2[i] = max(dp2[i],dp2[i + (1 << (j-1))]);
}
}
}
}
int askRMQ(int s,int e,int kind) {
if(kind == 1) {
return min(dp1[s],dp1[e - (1 << k) + 1]);
} else return max(dp2[s],dp2[e - (1 << k) + 1]);
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
k = log(double(m)) / log(double(2));
initRMQ();
printf("%d",askRMQ(1,m,1));
for(int i=2; i<=n-m+1; i++) {
printf(" %d", askRMQ(i,i+m-1,1));
}
puts("");
printf("%d",askRMQ(1,m,2));
for(int i=2; i<=n-m+1; i++) {
printf(" %d",askRMQ(i,i+m-1,2));
}
puts("");
return 0;
}
补充：软件开发 , C++ ,
