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;  
}