https://www.luogu.org/problemnew/show/P1440

题目描述

一个含有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

 #include <cstdio>

 #define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b) inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
const int N();
int n,m,st[N][],log2[N],t; int Presist()
{
read(n),read(m);
for(int i=; i<=n; ++i)
read(st[i][]),log2[i]=(<<t+==i)?++t:t;
for(int j=; <<j<=n; ++j)
for(int i=; i+(<<j)<=n+; ++i)
st[i][j]=min(st[i][j-],st[i+(<<j-)][j-]);
puts("");
for(int l,r=,mid; r<n; ++r)
{
l=max(r-m+,); mid=log2[r-l+];
printf("%d\n",min(st[l][mid],st[r-(<<mid)+][mid]));
}
return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}

80分 ST表

单调队列跑一边

 #include <cstdio>

 inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
const int N();
int n,m,a[N];
int head=,tail,que[N]; int Presist()
{
read(n),read(m);
for(int i=; i<=n; ++i)
{
read(a[i]); printf("%d\n",a[que[head]]);
for(; head<=tail&&a[que[tail]]>=a[i]; ) tail--;
for(que[++tail]=i; head<=tail&&que[head]<=i-m; ) head++;
}
return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
05-11 20:01