求教,萌新,菜鸡,全输出0啊啊啊

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

Palpitation_ @ 2019-07-29 12:59:00

RT,ST表,样例全输出0

#include<bits/stdc++.h>

using namespace std;
int a[100005],n,m,p[20][100005];int t=log2(n);int q[20][100005];

int querymax(int l,int r){
    int t=log2(r-l+1);
    return max(q[t][l],q[t][r-(1<<t)+1]);

}
void mmax(){
    for(int k=1;k<=t;k++){
        for(int i=1;i+(1<<k)-1<=n;i++){
            q[k][i]=max(q[k-1][i],q[k-1][i+(1<<(k-1))]);
        }
    }
}
int querymin(int l,int r){
    int t=log2(r-l+1);
    return min(p[t][l],p[t][r-(1<<t)+1]);
}
void mmin(){
    for(int k=1;k<=t;k++){
        for(int i=1;i+(1<<k)-1<=n;i++){
            p[k][i]=min(p[k-1][i],p[k-1][i+(1<<(k-1))]);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[0][i]);
        q[0][i]=p[0][i];
    }
    int l=1,r=m;
    mmin();
    for(int i=1;i<=n-m;i++){
        printf("%d ",querymin(l,r));
        l++,r++;
    }
    printf("\n");
    mmax();
    l=1,r=m;
    for(int i=1;i<=n-m;i++){
        printf("%d ",querymax(l,r));
        l++,r++;
    }
    return 0;
}

by Palpitation_ @ 2019-07-29 13:12:13

个人觉得没问题啊啊啊


by ZYF_B @ 2019-07-29 13:14:33

为什么你的t在n读入前就算了


by Palpitation_ @ 2019-07-29 13:17:13

@ZYF_B sb了QAQ


by Palpitation_ @ 2019-07-29 13:22:07

@ZYF_B 可还是有点WA了啊https://www.luogu.org/record/21753556


by ZYF_B @ 2019-07-29 14:07:50

N<=1e6...


by Palpitation_ @ 2019-08-18 20:05:54

@ZYF_B 同学ST表A了啊


|