首页 > 代码库 > luogu P1440 求m区间内的最小值

luogu P1440 求m区间内的最小值

2024-09-23 00:25:17   203人阅读

题目描述

一个含有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区间内的最小值


联系
我们