求助,线段树WA*8

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

dayi @ 2018-09-21 12:33:52

TLE我再优化qwq,为什么WA*8? https://www.luogu.org/recordnew/show/10767127

#include<iostream>
//#include<algorithm>
using namespace std;
#define max(x,y) (x>y)?x:y
#define min(x,y) (x<y)?x:y
#define maxn 1000005
#define INIT_CIN    \
    ios::sync_with_stdio(false);    \
    cin.tie(0);
int A[maxn],cnt=1,ans=0;
const int inf = 0x3f3f3f3f;
struct node{
    int lc,rc,sum,min,max;
    int add;
}a[maxn<<1];
inline void pushup(int u){
    a[u].min=min(a[a[u].lc].min,a[a[u].rc].min);
    a[u].max=max(a[a[u].lc].max,a[a[u].rc].min);
}
inline void build(int u,int l,int r){
    if(l==r){
        a[u].min=A[l],a[u].max=A[l];
        return ;
    }
    int mid=(l+r)>>1;
    a[u].lc=++cnt;
    build(a[u].lc,l,mid);
    a[u].rc=++cnt;
    build(a[u].rc,mid+1,r);
    pushup(u);
}
inline void query_max(int u,int l,int r,int ll,int rr){
    if(l==ll&&r==rr){
        ans=max(a[u].max,ans);
        return;
    }
    int mid=(l+r)>>1;
    if(rr<=mid)query_max(a[u].lc,l,mid,ll,rr);
    else if(ll>mid)query_max(a[u].rc,mid+1,r,ll,rr);
    else{
        query_max(a[u].lc,l,mid,ll,mid),query_max(a[u].rc,mid+1,r,mid+1,rr);
    }
}
inline void query_min(int u,int l,int r,int ll,int rr){
    if(l==ll&&r==rr){
        ans=min(a[u].min,ans);
        return;
    }
    int mid=(l+r)>>1;
    //pushdown
    if(rr<=mid)query_min(a[u].lc,l,mid,ll,rr);
    else if(ll>mid)query_min(a[u].rc,mid+1,r,ll,rr);
    else{
        query_min(a[u].lc,l,mid,ll,mid),query_min(a[u].rc,mid+1,r,mid+1,rr);
    }
}
int n,k;
int main()
{
    INIT_CIN;
    cin>>n>>k;for(int i=1;i<=n;++i){cin>>A[i];}
    build(1,1,n);
    int t=n-k+1;
    for(int i=1;i<=t;++i){//min
        register int l=i,r=i+k-1;
    //  cout<<"de:"<<l<<" "<<r; 
        ans=inf;
        query_min(1,1,n,l,r);
        cout<<ans<<" ";
    }cout<<endl;
    for(int i=1;i<=t;++i){//max
        register int l=i,r=i+k-1;
    //  cout<<"de:"<<l<<" "<<r<<endl;
        ans=-inf;query_max(1,1,n,l,r);cout<<ans<<" ";
    }
    return 0;
}

by royzhu @ 2018-09-21 13:54:33

你能AC两个点已经是奇迹


by royzhu @ 2018-09-21 13:57:07

else
{
    ans=min(query_min(a[u].lc,l,mid,ll,mid),ans),min(query_min(a[u].rc,mid+1,r,mid+1,rr),ans);
}

by royzhu @ 2018-09-21 13:57:54

发错了


by royzhu @ 2018-09-21 13:58:06

else
{
    ans=min(query_min(a[u].lc,l,mid,ll,mid),ans)
    ,ans=min(query_min(a[u].rc,mid+1,r,mid+1,rr),ans);
}

by dayi @ 2018-09-21 18:51:15

@royzhu 谢谢dalao回复我、

不过我还是没看懂为什么这样做..

这样直接递归到所在区间,然后更新最值不行嘛..为什么还要递归左孩子和右孩子捏..


by royzhu @ 2018-09-22 13:14:42

我搞错了, 问题不在这。


by royzhu @ 2018-09-22 13:16:08

你这里打错了

inline void pushup(int u){
    a[u].min=min(a[a[u].lc].min,a[a[u].rc].min);
    a[u].max=max(a[a[u].lc].max,a[a[u].rc].min);
}

应该是

inline void pushup(int u){
    a[u].min=min(a[a[u].lc].min,a[a[u].rc].min);
    a[u].max=max(a[a[u].lc].max,a[a[u].rc].max);
}

by dayi @ 2018-09-24 13:28:56

@royzhu 太感谢了!!!


|