如果30pts,AC on#1, #5, #6
查看原帖
如果30pts,AC on#1, #5, #6
728079
XuYueming楼主2023/10/7 19:26

在 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;
}
2023/10/7 19:26
加载中...