【例题】DP单调队列优化

/*
    LBR
    单调队列
    P:https://www.luogu.org/problem/show?pid=1440
    此代码会TLE 3个点，要改scanf（快一倍....）
*/
#include<bits/stdc++.h>
#define P pair<int,int>
using namespace std;
int n,m;
int d[2000001];
int ans[2000001];
P q[2000001];
void run()
{

    int l=0,r=-1;
    q[++r]=P(d[1],1);
    ans[1]=0;
    for(int i=2;i<=m;i++)
    {
        ans[i]=q[l].first;
        while(l<=r&&d[i]<=q[r].first)r--;
        q[++r]=P(d[i],i);
    }
    for(int i=m+1;i<=n;i++)
    {
        while(l<=r&&q[l].second<i-m)l++;
        ans[i]=q[l].first;
        while(l<=r&&d[i]<=q[r].first)r--;
        q[++r]=P(d[i],i);
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>d[i];
    }
    run();
    for(int i=1;i<=n;i++)
    {
       cout<<ans[i]<<endl;
    }
}