首页 > 代码库 > luogu P1440 求m区间内的最小值
luogu P1440 求m区间内的最小值
题目描述
一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。
输入输出格式
输入格式：第一行两个数n，m。
第二行，n个正整数，为所给定的数列。
输出格式：n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。
输入输出样例
输入样例#1：
6 27 8 1 4 3 2
输出样例#1：
077113
说明
【数据规模】
m≤n≤2000000
线段树
维护最小值
#include<cstdio>#include<iostream>#include<algorithm>using namespace std;#define N 8000006int a[N],sum[N];int read(){ int sum = 0, fg = 1; char c = getchar(); while(c < ‘0‘ || c > ‘9‘) { if (c == ‘-‘) fg = -1; c = getchar(); } while(c >= ‘0‘ && c <= ‘9‘) { sum = sum * 10 + c - ‘0‘; c = getchar(); } return sum * fg;}void update(int rt){ sum[rt]=min(sum[rt<<1],sum[rt<<1|1]);}void build(int l,int r,int rt){ if(l==r) { sum[rt]=a[l]; return; } int m=(l+r)>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); 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)>>1; if(nowl<=m)query(l,m,rt<<1); if(nowr>m)query(m+1,r,rt<<1|1);}int ans1; int main(){ int n,m; n=read(); m=read(); for(int i=1;i<=n;i++) a[i]=read(); build(1,n,1); for(int i=1;i<=n;i++) { if(i==1) { puts("0"); continue; } else { nowr=i-1; if(i-m>=1) nowl=i-m; else nowl=1; } ans=0x7fffffff; query(1,n,1); printf("%d\n",ans);//线段树 } return 0;}
luogu P1440 求m区间内的最小值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。