首先很容易想到差分约束

一个条件相当于 $x_i-x_j\le w(i,j)\iff x_i\le w(i,j)+x_j$，考虑从 $j$ 到 $i$ 连边，边权为 $w(i,j)$

考虑某个 $x_i-x_j$ 最小是多少，发现其实就是图中 $i\to j$ 的最短路的相反数。

因此，设 $\text{dis}(i,j)$ 表示 $i\to j$ 的最短路长度，那么我们只需要找到 $\min_{j\neq i}\text{dis}(i,j)$ 即可。

考虑分治。定义 $\text{solve}(l,r)$ 表示计算 $[l,r]$ 内每个点对 $[l,r]$ 内自己的贡献；设 $mid=(l+r)/2$，我们建一个源点 $s$ 并向每个 $x\in[l,mid]$ 连边，从 $s$ 开始跑 SPFA，就算出了 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。

同理也可以算出 $[mid+1,r]$ 到 $[l,mid]$ 的贡献；分治的边界是 $l=r$，此时直接返回即可。可以发现分治完成之后，我们就算出了 $[1,n]$ 中每个点的答案。

代码实现的方式大概是对每一位分 $0,1$ 考虑，和分治本质是等价的。

代码并不难写，不到 100 行，一张图就能截下来