关于此题的一个小想法

考虑boruvka算法。我们需要进行$O(n\log_2n)$次询问某个连通块内的某个点到其他连通块内的点的最小边权。

考虑如下做法：设当前点为$x$，我们需要知道$\min(a_x+a_y+|b_x-b_y|)=a_x+\min(a_y+|b_x-b_y|)$。考虑分$b_x>b_y$，$b_x\leq b_y$讨论。假设$b_x>b_y$（$b_x\leq b_y$）类似。我们要求$a_x+\min(a_y+b_x-b_y)=a_x+b_x+\min(a_y-b_y)$（$x,y$对应区间相交）。考虑给每个点$i$染色$c_i$（$c_i$是整数）。相同/不同连通块的颜色是相同/不同的。

考虑对$l_i,r_i$扫描线。（因为不扫描线要4个log）。在我们插入某个区间时，这个区间会对其他不和它在同一个连通块内的区间产生贡献。而这个区间的最小出边也会被所更新。可以用如下数据结构维护：这个结构支持每次对于一个点$x$，查询满足$b_x>b_y,c_x\neq c_y$（把$c_x\neq c_y$拆成$c_x>c_y$或者$c_x\leq c_y$，就变成了二维平面的查询）的点$y$的$a_y-b_y$的最小值，或者给定一个点$y$，将满足$b_x>b_y,c_x\neq c_y$（$c_x>c_y$或者$c_x\leq c_y$）的点$x$对$a_y-b_y$取最小值。可以用嵌套线段树维护（要先删除再插入，否则不相交的区间会互相产生贡献）。时间复杂度是3个log。

不知道能不能过