WA 后七个点并荣获 30pts 的另一种可能
查看原帖
WA 后七个点并荣获 30pts 的另一种可能
120324
Yansuan_HCl楼主2022/7/19 21:26

修改时向上跳重链,获取当前重链的时候,答案矩阵要从重链顶乘到重链底而不是从 u 开始乘。

正确代码:

void pathUpd(int u, int w) {
	inital[dfn[u]][1][2] += w - a[u];
	a[u] = w;
	while (u) {
		Matrix<1, 2> before, after; // 更改需要计算差值
		// 注意,这里有个大坑点!
		// 重链的 dp 值要一直乘到链顶而不是乘到 u 
		before = zero * query(dfn[top[u]], term[top[u]]);
		update(dfn[u]);
		after = zero * query(dfn[top[u]], term[top[u]]);
		u = fa[top[u]];
		
		inital[dfn[u]][1][1] += -max(before[1][1], before[1][2]) + max(after[1][1], after[1][2]);
		inital[dfn[u]][2][1] = inital[dfn[u]][1][1];
		inital[dfn[u]][1][2] += -before[1][1] + after[1][1];
	}
}

错误代码:

void pathUpd(int u, int w) {
	inital[dfn[u]][1][2] += w - a[u];
	a[u] = w;
	while (u) {
		Matrix<1, 2> before, after; // 更改需要计算差值
		before = zero * query(dfn[u], term[top[u]]);
		update(dfn[u]);
		after = zero * query(dfn[u], term[top[u]]);
		u = fa[top[u]];
		
		inital[dfn[u]][1][1] += -max(before[1][1], before[1][2]) + max(after[1][1], after[1][2]);
		inital[dfn[u]][2][1] = inital[dfn[u]][1][1];
		inital[dfn[u]][1][2] += -before[1][1] + after[1][1];
	}
}
2022/7/19 21:26
加载中...