被死亡凝视前还有一分钟去忘记了一切

[UNR 7]反重：求熵

好怪的题。

我们考虑一个一个消掉变量，现在考虑 \(x_n\)，我们会有一堆形如：\(x_n\leq x_i+a_{n,i}\) 或者 \(x_n\geq x_i-a_{i,n}\) 的限制，显然第一类限制给出了 \(x_n\) 的上界，第二类限制给出了 \(x_n\) 的下界，如果已经确定了 \(x_1\cdots x_{n-1}\)，只需要考虑两类限制中分别最紧的就行了。

我们枚举第一类限制中最紧的是 \(p\)，第二类限制中最紧的是 \(q\) ，那么就是要求：

• \(x_i+a_{n,i}\geq x_p+a_{n,p}\to x_p-x_i\leq a_{n,i}-a_{n,p}\)

• \(x_i-a_{i,n}\leq x_q-a_{q,n}\to x_i-x_q\leq a_{i,n}-a_{q,n}\)

• \(x_p+a_{n,p}\geq x_q-a_{q,n}\to x_q-x_p\leq a_{n,p}+a_{q,n}\)

这样就转化成了一堆和 \(n\) 无关的限制，然后乘上 \(n\) 的取值区间大小即可。