CYCPC R2 繁星坠海题解

写模拟赛的一道 F 题时想到的题目。但是这道题解法和那道题完全不同。

容易想到线段树优化建图，但是此题需要额外处理一个边权不同的问题。注意到这个距离函数有个美好的性质，对于任意 ，满足 。

我们考虑把一个点拆成两个点， 和 ，分别表示从左边和从右边到达 点。在这两个点之间连一条边权为 的双向边。

考虑一个点向右侧区间连边的情况。我们把边权拆成若干份。一个点 向线段树上节点 连边时，相当于先走到 左端点所在的位置（记作 ），这条边代价为 。假如这个节点要继续向右，走到节点的右子树中（记作 ，该节点的中点记作 ），那么就相当于从 走到 ，代价为 ，因此对于线段树上的每个节点，向其左子节点连一条权值为 的边，向其右子树连一条权值为 的边。

向左侧区间连边再另建一颗线段树即可。类似地，我们先走到节点上的右子树，然后在走向左子节点或者右子节点。对于这颗线段树的每个节点，先向其右子树连一条权值为 的边，再向其左子树连一条权值为 的边。

如果要连边的区间包括了自己，那就分成左右两部分分别连边。

区间向点连边的情况也类似，只需要改成从子节点向父节点连边即可。

时间复杂度 。

---

UPDATE：怎么有原题啊。其实这篇题解原本就在博客来着，因为要投题给 CYCPC R2 就删掉了。你甚至可以在 git history 里找到。