P1440 求m区间内的最小值--洛谷luogu

题目描述

一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。

输入输出格式

输入格式：

第一行两个数n，m。

第二行，n个正整数，为所给定的数列。

输出格式：

n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。

输入输出样例

输入样例#1： 

6 2

7 8 1 4 3 2

输出样例#1： 

0

7

7

1

1

3

说明

【数据规模】

m≤n≤2000000

ai​≤3×107

---------------------------------------

刚一看题

觉得这题特水

难道不是简单的ST表吗

于是自信满满的写了

于是发生了不可思议的事情

这是本题的部分代码，黄色部分（好像看不太清），必须写上+1才能过样例！

而这个写上就不过，好像必须省略

然而，书上模板代码都是有+1的，这我就懵了

然而这还不是最关键的

最关键的是

这次mle掉了

我可是精心溜边走得数组大小啊

那么肯定说明

st表并不是这道题的正解

但是我还要放我的错误ST表的代码

这是错误的代码啊！！！！！

#include<cstdio>

#include<iostream>

using namespace std;

int n,m;

int d[][];

void RMQ()

{

    for(int j = ;(<<j)<=n;j++)

        for(int i = ;i+(<<j)-<n;i++)

            d[i][j] = min(d[i][j-],d[i+(<<(j-))][j-]);

}

void fid(int l,int r)

{

    int k = ;

    while(<<(k+) <= r-l+)

    {

        k++;

    }

    printf("%d\n",min(d[l][k],d[r-(<<k)+][k]));

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = ;i < n;i++)

        scanf("%d",&d[i][]);

    RMQ();

    printf("0\n");

    int ans = ;

    for(int i = ;i <= m;i++)

        fid(,i-);

    for(int i = m+;i < n;i++)

        fid(i-m,i-);

    return ;

}

所以去学习了！！！

----------------------------------------------------

而正解是

单调队列

线性时间复杂度

#include <bits/stdc++.h>

using namespace std;

const int maxn=;

struct node{

    int v,id;

}a[maxn];

int ans[maxn];

int n,m;

deque<node> dq;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<n;i++)

    {

        scanf("%d",&a[i].v);

        a[i].id=i;

    }

    ans[]=;

    for(int i=;i<n;i++)

    {

        //队首是价值最高的，队尾是最年轻的

        while(!dq.empty() && dq.back().v>=a[i-].v)

            dq.pop_back();    //比新元素老，价值还不如新元素的，一律弹掉

        dq.push_back(a[i-]);

        while(dq.front().id<i-m)

            dq.pop_front();       //不管价值如何，老死的一律弹掉

        ans[i]=dq.front().v;   //front()就是最小元素值

    }

    for(int i=;i<n;i++)

        printf("%d\n",ans[i]);

    return ;

}