拓扑排序
差分约束
要求构造长度为 \(n\) 的序列使其满足 \(m\) 条形如 \(a_i - a_j \le x_k\) 或 \(a_i < a_j\) 的约束。
对于每个约束 \(a_i - a_j \le x_k\) 由 \(j\) 向 \(i\) 连一条长度为 \(x_k\) 的有向边，若图中存在负环，则无解。
若约束全部为 \(a_i < a_j\) 形式（即 \(x\) 全部为 \(0\)），由 \(i\) 向 \(j\) 连一条有向边，若图中存在环，则无解，否则构成一个有向无环图。
线段树优化建图。
点击查看代码
``` nothing here. ```反向最大字典序
在 DAG 拓扑序中要求第 \(i\) 个数在前 \(i - 1\) 个数尽量优先的情况下尽量优先，最终答案就是反图中字典序最大的拓扑序的反向序列。
感性理解。
证明：不会。