蒟蒻求解st50分,re和wa..救救蒟蒻

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

醉了酒的李白 @ 2018-12-24 13:21:02

#include<iostream>
using namespace std;
int n,k;
int log[1000];
int mx[1000100][15],mn[1000100][15];
//int a[1000100];
int z;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>mn[i][0];
        mx[i][0]=mn[i][0];
    }
    log[0]=-1;
    for(int i=1;i<=100;i++)
        log[i]=log[i/2]+1;
    //for(int i=1;i<=100;i++)
    //  cout<<log[i]<<" ";
    for(int j=1;j<=10;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
        }
    for(int i=1;i+k-1<=n;i++)
        cout<<min(mn[i][log[k]],mn[i+k-(1<<(log[k]))][log[k]])<<" ";
    cout<<endl;
    for(int i=1;i+k-1<=n;i++)
        cout<<max(mx[i][log[k]],mx[i+k-(1<<(log[k]))][log[k]])<<" ";
}

by _Sein @ 2018-12-24 13:34:51

这道题不是用单调队列嘛


by 醉了酒的李白 @ 2018-12-24 13:43:28

@lb2003 是的,但是dalao说st表也可以水过


by ikka @ 2018-12-28 15:41:19

第二维开到21试下,\lfloor log_2{1e6}\rfloor=19,k很大数组会越界。


|