本地没炸，但RE 0pts求条

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

Ben幻影 @ 2023-08-04 16:14:47

求条

本地运行#1没有炸，可是却RE，悬一关，禁止启动元神。 如果觉得违规请先告知谢谢。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5000010;
ll n,m,a[N],l[N],r[N];
list<ll> L;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        while(L.size()&&a[i]<a[L.back()]){
            L.pop_back();
        }
        while(L.size()&&i-L.front()>=m) L.pop_front();
        if(L.size()==0) r[a[i]]=0;
        L.push_back(i);
        if(i>=m) cout<<a[L.front()]<<" ";
    }
    cout<<endl;
    while(!L.empty()) L.pop_back();
    for(int i=1;i<=n;i++){
        while(L.size()&&a[i]>a[L.back()]){
            L.pop_back();
        }
        while(L.size()&&i-L.front()>=m) L.pop_front();
        if(L.size()==0) r[a[i]]=0;
        L.push_back(i);
        if(i>=m) cout<<a[L.front()]<<" ";
    }
    return 0;
}

by chris731 @ 2023-08-04 16:22:36

const int N=9000010;

n大一点可得30分

by XuYueming @ 2023-08-04 16:36:51

这样不RE，等我改完TLE再详细说

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=6000010;
ll n,m,a[N];
list<ll> L;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        while(L.size()&&a[i]<=a[L.back()]){
            L.pop_back();
        }
        while(L.size()&&i-L.front()>=m) L.pop_front();
//        if(L.size()==0) r[a[i]]=0;
        L.push_back(i);
        if(i>=m) cout<<a[L.front()]<<" ";
    }
    cout<<endl;
    while(!L.empty()) L.pop_back();
    for(int i=1;i<=n;i++){
        while(L.size()&&a[i]>=a[L.back()]){
            L.pop_back();
        }
        while(L.size()&&i-L.front()>=m) L.pop_front();
//        if(L.size()==0) r[a[i]]=0;
        L.push_back(i);
        if(i>=m) cout<<a[L.front()]<<" ";
    }
    return 0;
}

by XuYueming @ 2023-08-04 16:40:11

开O2过

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=6000010;
ll n,m,a[N];
list<ll> L, L2;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        while(L.size()&&a[i]<=a[L.back()]){
            L.pop_back();
        }
        while(L.size()&&i-L.front()>=m) L.pop_front();
//        if(L.size()==0) r[a[i]]=0;
        L.push_back(i);
        if(i>=m) cout<<a[L.front()]<<" ";
    }
    cout<<endl;
//    while(!L.empty()) L.pop_back();
    for(int i=1;i<=n;i++){
        while(L2.size()&&a[i]>=a[L2.back()]){
            L2.pop_back();
        }
        while(L2.size()&&i-L2.front()>=m) L2.pop_front();
//        if(L.size()==0) r[a[i]]=0;
        L2.push_back(i);
        if(i>=m) cout<<a[L2.front()]<<" ";
    }
    return 0;
}

by XuYueming @ 2023-08-04 16:42:40

首先，~~众所周知~~，STL不开O2龟速……所以不开O2建议手写队列，这样清空的时候也只用给两个变量赋值就行了（head和tail）。
没看出l，r有什么用
题目中N的范围看仔细！

by XuYueming @ 2023-08-04 16:42:57

@Ben幻影

by XuYueming @ 2023-08-04 17:15:20

@Ben幻影懂了吗？

by Ben幻影 @ 2023-08-05 00:30:06

@XuYueming 懂了，马上关注。

回第二个问题：机房编的时候用之前的代码复制过来的（就是要个main和头文件）导致历史遗留