为什么会超时????

P1886 滑动窗口 /【模板】单调队列

_zjr @ 2018-01-07 23:24:12

下面是我写的RMQ(本蒟蒻只会用RMQ)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
const int mxn=1000001;
using namespace std;
int q[mxn][20],p[mxn][20];
int n,k;
int max(int a,int b){
    if(a>b) return a;
    else return b;
}
int min(int a,int b){
    if(a<b) return a;
    else return b;
}
int find(int l,int r){
    int i; 
    for(int i=1;i<=16;i++){
        if(pow(2,i)>r){
            i-=1;
        }
    }
    return max(q[l][i],q[l+r-(int)pow(2,i)][i]);
}
int find2(int l,int r){
    int i;
    for(int i=1;i<=16;i++){
        if(pow(2,i)>r){
            i-=1;
        }
    }
    return min(p[l][i],p[l+r-(int)pow(2,i)][i]);
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>q[i][0];
        p[i][0]=q[i][0];
    }
    for(int i=1;i<=16;i++){
        for(int j=1;j<=n;j++){
            q[j][i]=max(q[j][i-1],q[j+(int)pow(2,i-1)][i-1]);
            p[j][i]=min(p[j][i-1],p[j+(int)pow(2,i-1)][i-1]);
        }
    }
    for(int j=1;j<=n;j++) cout<<find2(j,k)<<' ';
    cout<<endl;
    for(int j=1;j<=n;j++) cout<<find(j,k)<<' ';
    return 0;
}
然后,,,所有点超时

by iodwad @ 2018-01-07 23:38:10

你每次手动算log2肯定超时了呀。。。这个东西可以预处理出来的


by λᴉʍ @ 2018-01-08 07:42:06

你预处理出log应该就不会T了


by 微雨燕双飞 @ 2018-01-31 20:18:50

哇,第一次看人RMQ手动写log的(虽然我曾经也这样),改掉应该就没事了。


|