笔记汇总

差分约束的难点就是不等式，

对于一个不等式，我们有：
①对称性；
②传递性；
③加法单调性，即同向不等式可加性；
④乘法单调性；
⑤同向正值不等式可乘性；
⑥正值不等式可乘方；
⑦正值不等式可开方；
⑧倒数法则；
⑨除法异号。

对于一道题目，最重要的就是找到不等式关系。

在没有关系前，图就是乱序的。

简单题

多，少，至少，至多。

一次是两个人比较，可能会将不等式变式，

$A < B + C, A - B < C, B < C - A$（$C$ 为常数）

找到变量与常数，结合未知数表示出来就可以变式了。

由于差分约束维护不等式，所以等式为 （A==B）=（A>=B && A<=B）

中等题

结合实际情况，人数不能为负，

集合本身的序数关系，正序，倒序，某类都在某类右边，

这些可以表示为一系列的不等式来建图。

与前缀和、差分的集合，（区间转化端点）

我们可以维护前缀和的差分，

$S_i >= S_{i-1} + d$

$S_b >= S_{a-1} + c$

可以维护区间内是否满足至少有 $c$ 个数满足不等关系，

以及类似问题。