考场上 10 min 读题切题，似乎和很多人做法不太一样（？不过明显本质相同。

我们考虑从答案入手。如果尝试让一个答案 k 成为中位数，那么你会怎么选？

我们可以把区间分为三种，我们记录比 k 低的数字的个数范围， 等于 $k$ 的数字的个数范围，比 k 高的数字的个数范围：

第一种是 r<k，此时无论如何选，都比 k 低。

第二种是 l>k，此时无论如何选，都比 k 高。

否则就是第三种，区间可以包含 k。贪心考虑一定选择 k 更好。

而 $k$ 越多越好，所以只需要记录等于 k 的数字的上限。

然后考虑第一种和第二种会抵消。只需记录一个即可。例如第二种 [1,3] 个可以看作是第一种 [-3,-1] 个。

此时在范围里找一个绝对值最小的数和 k 的个数上限比就好了。（记得特判，第一种和第二种一个是严格比较一个是不严格比较）

所以只需要枚举每个可能成为答案的数字就好了。可是值域很大。考虑处理这三个序列的差分操作进行排序，然后依次处理。如果这一格的差分都处理完了，此时如果满足条件就直接对一段区间统计答案。本质上就是带权值离散化。

然后你就做完了。复杂度 O(n log n) ，六倍常数。