题目描述
一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。
输入输出格式
输入格式：
第一行两个数n，m。
第二行，n个正整数，为所给定的数列。
输出格式：
n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。
输入输出样例
说明
【数据规模】
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 ;
}