线段树区间合并的一些疑问
查看原帖
线段树区间合并的一些疑问
1201076
senak楼主2024/5/13 21:01

我看很多题解 sum表示区间最大连续空房数,lsum和rsum表示从左开始或从右开始的最大连续空房数

struct Node{
    int lsum, rsum, sum, lazy;
}t[N<<2];

那么对于pushup操作 如果说要取

t[p].sum=t[p * 2].rsum + t[p * 2 + 1].lsum

那么是否应该满足左儿子区间右端点=右儿子区间左端点=0?因为这才保证区间空房是连续的.

void pushup(int p, int l, int r) {
    t[p].sum = max(max(t[p * 2].sum, t[p * 2 + 1].sum), t[p * 2].rsum + t[p * 2 + 1].lsum);

    //这个地方是否应该先满足两个感叹号等于0才可以t[p * 2].rsum + t[p * 2 + 1].lsum?
    //L      ! !      R
    //00000111 11000000
}
2024/5/13 21:01
加载中...