CF1863E
你在玩一个游戏，要完成 \(n\) 个任务。其中对于每个任务 \(i\)，它只能在某一天的第 \(h_i\) 时刻完成。游戏每天有 \(k\) 个小时，分别编号为 \(0,1,...k-1\)。
给出 \(m\) 对任务间的依赖关系，\((a_i,b_i)\) 表示 \(a_i\) 必须比 \(b_i\) 先完成。保证依赖关系不形成环。
完成任务不需要时间，也就是说可以在同一天的同一时刻先后完成多个任务。
求完成所有任务所需的最短时间。这里的时间定义为：完成最后一个任务的时刻 与 开始第一个任务的时刻 之差。
多组数据，\(T\le 10^5\)，\(\sum n,m\le 2\times 10^5\)，\(k\le 10^9\)。
-
如果你认为直接跑一边 \(dp\) 就可以轻松解决的话，请注意最终题目要求的值
-
如果还不理解，可以手玩第 \(4\) 个样例
-
in: 5 0 1000 8 800 555 35 35 ans: 480 -
因为我们可以第 \(1\) 天完成
555，第 \(2\) 天完成8 35 35 800。最终答案为 \(1035-555=480\)
-
因为我们容易发现，对于每一条边，他时间的差值是固定的，我们把这个作为边权
-
例如从 \(h_1=3 \to h_2=5\)，那我们可以令边 \((1,2)\) 的边权为 \(2\)；相反的，如果 \(h_1 = 5, h_2 = 3\)，边权应为 \(k-2\)，这样我们可以得到一个有边权的 \(DAG\)
-
如果我们枚举开始的时间是 \(x\)，那对于每一个 \(x\) 我们可以在原图跑一个 \(O(n)\) 的最长路，这显然是正确的
-
我们时间无法优化的原因是枚举的 \(x\) 是跑最长路的基础，我们改变 \(x\) 就一定会改变最长路过程中的值，但这是可以避免的，我们只需要对返图跑最长路即可，这样我们就可以得到从出度为 \(0\) 的点到入度为 \(0\) 的点的最长路，我们可以记作 \(d_i\)
-
因为我们是对反图跑最长路，因此我们最长路得到的值 \(d_i\) 是与 \(x\) 无关的，我们考虑怎么把 \(x\) 的贡献加上去
-
对于枚举的一个 \(x\)，我们把所有入度为 \(0\) 的点分为两类处理
-
\(h_i < x\)，这一类要放到第二天开始处理，因此答案为 \(k - (x - h_i) + d_i\)
-
\(h_i \geq x\)，这一类第一天就开始处理，答案为 \(h_i - x + d_i\)
-
-
我们对这两种情况取 \(\max\) 得到的值即为当前 \(x\) 下的答案，我们对于所有 \(x\) 求 \(\min\) 即可
-
虽然直接暴力的做还是 \(O(n^2)\) 的，但仔细想想就发现这很好优化，我们把第一、二种情况的 \(-x\) 提出来，做一个前缀后缀的 \(\max\)，就可以 \(O(n)\) 的快速合并答案
-
最终复杂度 \(O(n)\)