求助,80分8,9tle

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

juruolht @ 2022-06-20 08:54:47

#include<bits/stdc++.h>
using namespace std;
int a[1000007];
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n-m+1;i++){
        int maxi=a[i];
        for(int j=i;j<=i+m-1;j++){
            maxi=min(maxi,a[j]);
        }
        printf("%d ",maxi);
    }
    cout<<endl;
    for(int i=m;i<=n;i++){
        int maxi=a[i];
        for(int j=i-m+1;j<=i;j++){
            maxi=max(maxi,a[j]);
        }
        printf("%d ",maxi);
    } 
    return 0;
}

by 天南星魔芋 @ 2022-06-20 08:56:26

为什么你觉得 O(n×k) 可以过


by Dream_weavers @ 2022-06-20 08:56:32

这是数据结构题啊,不是暴力能过的

正解:单调队列、ST表、线段树等


by Eason2009 @ 2022-06-20 08:56:55

您觉得这题暴力能过???


by juruolht @ 2022-06-20 08:58:45

。OK太久没刷题了,全忘光了我去看看线段树怎么写


by Dream_weavers @ 2022-06-20 08:58:46

最多要 O(k\times\log n)


by lanretE @ 2022-06-20 08:58:52

没看到这是 单调队列 模板?


by Ruiqun2009 @ 2022-06-20 09:49:06

odt?


by ningago @ 2022-06-20 09:56:04

1e6跑线段树,常数逆天


|