求助,对拍了好久都没错,为什么还会有点wa。。。

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

trouble_ @ 2018-03-09 18:25:58

#include<iostream>
#include<cstdio>
#define N 10000001
using namespace std;
int n,m;
int mmin,mmax;
int w[4*N],fm[4*N],fx[4*N];
int pushup1(int x)
{
    fm[x]=min(fm[x<<1],fm[x<<1|1]);
}
int pushup2(int x)
{
    fx[x]=max(fx[x<<1],fx[x<<1|1]);
}
void cc1(int l,int r,int x)
{
    if(fm[x]!=0)
    return;
    if(l==r)
    {
        fm[x]=w[l];
        return;
    }
    int mid=(l+r)>>1;
    cc1(l,mid,x<<1);
    cc1(mid+1,r,x<<1|1);
    pushup1(x);
}
void cc2(int l,int r,int x)
{
    if(fx[x]!=0)
    return;
    if(l==r)
    {
        fx[x]=w[l];
        return;
    }
    int mid=(l+r)>>1;
    cc2(l,mid,x<<1);
    cc2(mid+1,r,x<<1|1);
    pushup2(x);
}
int cz1(int L,int R,int l,int r,int x)
{
    if(L<=l&&r<=R)
    return fm[x];
    int mid=(l+r)>>1;
    if(L<=mid)
    mmin=min(mmin,cz1(L,R,l,mid,x<<1));
    if(R>mid)
    mmin=min(mmin,cz1(L,R,mid+1,r,x<<1|1));
    return mmin;
}
int cz2(int L,int R,int l,int r,int x)
{
    if(L<=l&&r<=R)
    return fx[x];
    int mid=(l+r)>>1;
    if(L<=mid)
    mmax=max(mmax,cz2(L,R,l,mid,x<<1));
    if(R>mid)
    mmax=max(mmax,cz2(L,R,mid+1,r,x<<1|1));
    return mmax;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&w[i]);
    cc1(1,n,1);
    cc2(1,n,1);
    for(int i=1;i<=n-m+1;i++)
    {
        mmin=1234567809;
        printf("%d ",cz1(i,i+m-1,1,n,1));
    }
    cout<<endl;
    for(int i=1;i<=n-m+1;i++)
    {
        mmax=0;
        printf("%d ",cz2(i,i+m-1,1,n,1));
    }
}

by Iowa_BattleShip @ 2018-03-09 18:31:37

mmax初始化为极小值


by Iowa_BattleShip @ 2018-03-09 18:31:45

@trouble_


by trouble_ @ 2018-03-10 19:24:35

@Iowa_BattleShip 谢谢啦


|