求大神指点

P1886 滑动窗口 /【模板】单调队列

Coco_T @ 2016-12-27 19:09:41

一直70分,把最大值和最小值改成long long 就会MLE。。。QAQ 不知道哪里有问题

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
    int le,ri,mi,ma;
};
node t[6000100];  //数组开4倍
int a[1000001];
int n,k;
int build(int x,int l,int r)
{
    t[x].le=l;
    t[x].ri=r;
    if (l==r)
    {
       t[x].ma=a[l];
       t[x].mi=a[l];
       return 0;
    }
    build(x*2,l,(l+r)/2);
    build(x*2+1,(l+r)/2+1,r);
    t[x].mi=min(t[x*2].mi,t[x*2+1].mi);
    t[x].ma=max(t[x*2].ma,t[x*2+1].ma);
}
int askmin(int x,int l,int r)
{
    if (t[x].le>=l&&t[x].ri<=r)
       return t[x].mi;
    if (t[x].le>r||t[x].ri<l)
       return 1073741824;
    return min(askmin(x*2,l,r),askmin(x*2+1,l,r));
}
int askmax(int x,int l,int r)
{
    if (t[x].le>=l&&t[x].ri<=r)
       return t[x].ma;
    if (t[x].le>r||t[x].ri<l)
       return 0;
    return max(askmax(x*2,l,r),askmax(x*2+1,l,r));
}
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);
    for (int i=1;i<=n-k+1;i++)
        printf("%d ",askmin(1,i,i+k-1));
    printf("\n");
    for (int i=1;i<=n-k+1;i++)
        printf("%d ",askmax(1,i,i+k-1));
    return 0;
}

by joyemang33 @ 2016-12-27 19:56:32

此题单调即可,线段树小题大做


|