警钟撅烂:关于锣鼓深进代码自己写后50pts

P1253 扶苏的问题

chillLee @ 2023-10-13 12:25:36

由于模板线段树的 w_u 维护的是一个区间和。在区间查询时,当判断 outofrange(l,r,L,R) 为真,会返回 0 ,但是由于此题维护的是最大值,返回 0 可能会导致 0w_u 大的情况发生,进而使区间最大值为负数时无法维护。
故而,当 outofrange(l,r,L,R) 为真,应该返回 -INF 而非 0

ll qjcx(int u,int l,int r,int L,int R){
    if(inrange(l,r,L,R))
        return w[u];
    else if(outofrange(l,r,L,R))return -INF; //!!
    else {
    int mid=(l+r)>>1;
    pushdown(u,l,r);
    return max( qjcx(u*2,l,mid,L,R) , qjcx(u*2+1,mid+1,r,L,R) );
    }   
}

by Chilllee_Qiuli @ 2023-12-01 19:30:47

很有用!


|