U603203 旅行题解

原题链接。

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

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

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

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

向左侧区间连边再另建一颗线段树即可。

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

时间复杂度 （应该是）。