在 pushup 中我们会对最大值在左右子树进行判断,此处有错误写法。
错误写法如下:
void pushdown(int idx){
if (!tree[idx].addlazy && !tree[idx].mxaddlazy && !tree[idx].maxaddlazy && !tree[idx].mxmaxaddlazy) return;
int maxx = max(tree[lson].max, tree[rson].max);
if (tree[lson].max == maxx){
update(lson, tree[idx].maxaddlazy, tree[idx].addlazy, tree[idx].mxmaxaddlazy, tree[idx].mxaddlazy);
update(rson, tree[idx].addlazy, tree[idx].addlazy, tree[idx].mxaddlazy, tree[idx].mxaddlazy);
} else {
update(lson, tree[idx].addlazy, tree[idx].addlazy, tree[idx].mxaddlazy, tree[idx].mxaddlazy);
update(rson, tree[idx].maxaddlazy, tree[idx].addlazy, tree[idx].mxmaxaddlazy, tree[idx].mxaddlazy);
}
tree[idx].addlazy = tree[idx].mxaddlazy = 0;
tree[idx].maxaddlazy = tree[idx].mxmaxaddlazy = 0;
}
其中我们忽略了最大值同时在左右子树的情况,故应该修改如下:
void pushdown(int idx){
if (!tree[idx].addlazy && !tree[idx].mxaddlazy && !tree[idx].maxaddlazy && !tree[idx].mxmaxaddlazy) return;
int maxx = max(tree[lson].max, tree[rson].max);
if (tree[lson].max == maxx) update(lson, tree[idx].maxaddlazy, tree[idx].addlazy, tree[idx].mxmaxaddlazy, tree[idx].mxaddlazy);
else update(lson, tree[idx].addlazy, tree[idx].addlazy, tree[idx].mxaddlazy, tree[idx].mxaddlazy);
if (tree[rson].max == maxx) update(rson, tree[idx].maxaddlazy, tree[idx].addlazy, tree[idx].mxmaxaddlazy, tree[idx].mxaddlazy);
else update(rson, tree[idx].addlazy, tree[idx].addlazy, tree[idx].mxaddlazy, tree[idx].mxaddlazy);
tree[idx].addlazy = tree[idx].mxaddlazy = 0;
tree[idx].maxaddlazy = tree[idx].mxmaxaddlazy = 0;
}