洛谷P1886题解

题目链接

献上一发线段树写法（线段树万岁）

建两次树，一次存最小值，一次存最大值

最后一个点极限卡时限980ms

#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
inline int Read()//快读
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
struct Tree 
{
    int l,r,dat;
    Tree() 
    {
        l=r=0;
        dat=0;
    }
}a[(N<<2)+10];
int num[N+10];
void Buildmin(int l,int r,int s)//建立存储最小值的线段树
{
    a[s].l=l;
    a[s].r=r;
    if(l==r)
    {
        a[s].dat=num[l];
        return;
    }
    int mid=(l+r)>>1;
    Buildmin(l,mid,s<<1);
    Buildmin(mid+1,r,s<<1|1);
    a[s].dat=min(a[s<<1].dat,a[s<<1|1].dat);
}
void Buildmax(int l,int r,int s)//建立存储最大值的线段树
{
    a[s].l=l;
    a[s].r=r;
    if(l==r)
    {
        a[s].dat=num[l];
        return;
    }
    int mid=(l+r)>>1;
    Buildmax(l,mid,s<<1);
    Buildmax(mid+1,r,s<<1|1);
    a[s].dat=max(a[s<<1].dat,a[s<<1|1].dat);
}
int querymax(int l,int r,int s)//查询区间[l,r]最大值
{
    int ans=INT_MIN;
    if(a[s].l>=l&&a[s].r<=r) return a[s].dat;
    if(a[s<<1].r>=l) ans=max(ans,querymax(l,r,s<<1));
    if(a[s<<1|1].l<=r) ans=max(ans,querymax(l,r,s<<1|1));
    return ans;
}
int querymin(int l,int r,int s)//查询区间[l,r]最小值
{
    int ans=INT_MAX;
    if(a[s].l>=l&&a[s].r<=r) return a[s].dat;
    if(a[s<<1].r>=l) ans=min(ans,querymin(l,r,s<<1));
    if(a[s<<1|1].l<=r) ans=min(ans,querymin(l,r,s<<1|1));
    return ans;
}
int main()
{
    int n=Read(),k=Read();
    int from=1,to=1+k-1;//from:窗口的左端点 to:窗口的右端点
    for(int i=1;i<=n;i++) num[i]=Read();
    Buildmin(1,n,1);//第一次建树，存最小值
    while(to<=n)
    {
        printf("%d ",querymin(from,to,1));
        from++;
        to++;
    }
    puts("");
    from=1,to=1+k-1;
    Buildmax(1,n,1);//第二次建树，存最大值
    while(to<=n)
    {
        printf("%d ",querymax(from,to,1));
        from++;
        to++;
    }
    return 0;
}

洛谷P1886题解

原文：https://www.cnblogs.com/juruo-zzt/p/12162872.html