Link
题解
首先忽略掉同侧的询问。
对于 \(K=1\)，它其实就是问一个点到其它点的距离之和最小值，直接找到中位数然后计算即可。
对于一条路线，我们可以发现，如果建的桥里这两个端点的中点越近，那么这条路线的长度就越短。
所以对于 \(K=2\)，我们需先将每条路线按照两个端点的坐标之和排序，并且将它们分成两部分，这样就变成了两个 \(K=1\) 的问题。
之后你要找一个分界点使得答案最小，然后需要动态求出前缀和后缀的中位数。
使用对顶堆即可，时间复杂度为 \(O(n\log n)\)。
代码
http://www.nfls.com.cn:10611/submission/212297
标签：luogu,P3644,中位数,APIO2015,八邻,旁之桥 From： https://www.cnblogs.com/CCPSDCGK/p/16755926.html