为什么这题用倍增会有两个点超时???求问大佬。。

P1440 求m区间内的最小值

MANCHERSTER @ 2017-08-24 08:12:17

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn=2000001;

int dp[maxn][20];

int n,m; 

void ST(){
    int i,j;
    for(j=1;(1<<j)<=n;j++){
        for(i=1;i+(1<<j)-1<=n;i++){
            if(dp[i][j-1]<dp[i+(1<<(j-1))][j-1]){
                dp[i][j]=dp[i][j-1];
            }
            else{
                dp[i][j]=dp[i+(1<<(j-1))][j-1];
            }
        }
    }
}

int RMQ(int L,int R){
    int len=R-L+1;
    int k=0;
    while((1<<(k+1)<=len)){
        k++;
    }
    int ans;
    if(dp[L][k]<dp[R-(1<<k)+1][k]){
        ans=dp[L][k];
    }
    else{
        ans=dp[R-(1<<k)+1][k];
    }
    return ans;
}

int main(){
    int i;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&dp[i][0]);
    }
    printf("0\n");
    ST();
    for(i=2;i<=n;i++){
        int l,r;
        r=i-1;
        l=i-m;
        if(l<=0){
            l=1;
        }
        printf("%d\n",RMQ(l,r));
    }
    return 0;
}

by cszmc2004 @ 2017-08-24 08:28:14

倍增是nlogn的


by cszmc2004 @ 2017-09-06 20:58:45

这题数据强度不小


by 青衫白叙 @ 2017-10-07 22:03:49

建议单调队列 + 二分


by 青石巷 @ 2017-10-17 20:40:38

@青衫白叙 不是纯单调队列就好了吗……为什么会有二分……


by 青衫白叙 @ 2017-10-17 20:42:39

@青石巷 因为要刷榜啊(逃)


by 青衫白叙 @ 2017-10-17 20:43:21

@青石巷 其实是可以二分插入位置的,可是复杂度会很玄学。。。


|