BZOJ3945 : 无聊的邮递员

因为两个人方案的对称性，可以将$k$除以2，转化为在$n-1$个间隔中设置若干断点，求第$k$小的增量。对于选中的相邻的断点$(a,a+1)$和$(b,b+1)$，增量为$|x_a-x_{b+1}|$。将绝对值拆开，用可持久化权值线段树优化建图，然后求$k$短路即可。时间复杂度$O(n\log