WA 后七个点并荣获 30 pts 的另一种可能
查看原帖
WA 后七个点并荣获 30 pts 的另一种可能
554746
yiming564楼主2024/7/3 20:10

如果你的代码像我一样,需要显式地维护每个节点的点权(来算重链的链尾向量 ∣0,w∣|0, w|),在写单点修改时要注意更新点权 ww 的顺序

void modify(node_t *u, int x)
{
	node_t *bak = u;
	M[u->start][1][0] += x - w[real(u)];
	while (u->head->parent)
	{
		auto next = u->head->parent;
		auto before = query(u->head);
		M[next->start][0][0] = M[next->start][0][1] = M[next->start][0][0] - before.max();
		M[next->start][1][0] -= before[0];
		tree.set(tree.root, u->start, M[u->start]);
		if (u == u->tail)	// update here
			w[real(u)] = x;
		auto after = query(u->head);
		M[next->start][0][0] = M[next->start][0][1] = M[next->start][0][0] + after.max();
		M[next->start][1][0] += after[0];
		u = next;
	}
	w[real(bak)] = x;	// update here
	tree.set(tree.root, u->start, M[u->start]);
}

不过我感觉这么写似乎写丑了

2024/7/3 20:10
加载中...