警示后人:如果你20pts WA #1 #4
查看原帖
警示后人:如果你20pts WA #1 #4
732906
4BboIkm7h楼主2024/12/19 17:05

如果你使用动态开点线段树,进行 QSQM 两个查询操作时,尝试在函数外将当前的根节点编号作为参数传入,在函数内,对于线段树上的区间查询操作,直接把传入的编号作为查询的根节点。例如:

ll query_dis_sum(int r, int u, int v) {
	ll res = 0;
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		res += query_sum(r, 1, n, dfn[top[u]], dfn[u]); //直接将传入的r作为根
		u = fa[top[u]];
	}
	if (dep[u] > dep[v]) swap(u, v);
	res += query_sum(r, 1, n, dfn[u], dfn[v]); //同上
	return res;
}

在外面传进去: query_dis_sum(root[c[u]], u, v)

我的 WA\text{WA} 原因:

ll query_dis_sum(int u, int v) {
	ll res = 0;
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		res += query_sum(root[c[u]], 1, n, dfn[top[u]], dfn[u]); 一直使用了root[c[u]]
		u = fa[top[u]];
	}
	if (dep[u] > dep[v]) swap(u, v);
	res += query_sum(root[c[u]], 1, n, dfn[u], dfn[v]);
	return res;
}

具体原因本蒟蒻也不是很懂,还请各位神犇解答

WA记录

2024/12/19 17:05
加载中...