题目描述
一个含有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>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 8000006
int a[N],sum[N]; int read()
{
int sum = , fg = ; char c = getchar();
while(c < '' || c > '') { if (c == '-') fg = -; c = getchar(); }
while(c >= '' && c <= '') { sum = sum * + c - ''; c = getchar(); }
return sum * fg;
} void update(int rt)
{
sum[rt]=min(sum[rt<<],sum[rt<<|]);
} void build(int l,int r,int rt)
{
if(l==r)
{
sum[rt]=a[l];
return;
}
int m=(l+r)>>;
build(l,m,rt<<);
build(m+,r,rt<<|);
update(rt);
}
int ans;
int nowr,nowl; void query(int l,int r,int rt){
if(nowr>=r&&nowl<=l)
{
ans=min(ans,sum[rt]);return ;
}
int m=(r+l)>>;
if(nowl<=m)query(l,m,rt<<);
if(nowr>m)query(m+,r,rt<<|);
} int ans1;
int main()
{
int n,m;
n=read();
m=read();
for(int i=;i<=n;i++)
a[i]=read();
build(,n,);
for(int i=;i<=n;i++)
{
if(i==)
{
puts("");
continue;
}
else
{
nowr=i-;
if(i-m>=)
nowl=i-m;
else nowl=;
}
ans=0x7fffffff;
query(,n,);
printf("%d\n",ans);//线段树
}
return ;
}