T1
只考虑连 \(a_u \leq a_v\) 的边，把所有边按照边权从小到大排序，跑一遍 dfs 求出最长路即可。
T2
你发现这种要求满足限制的题，且可以通过 \(x_r - x_l = d_i\) 构造关系。直接考虑差分约束，如果说出现当前 \(u,v\) 距离与之前所求矛盾则无解。根据 \(\begin{cases}x_r - x_l \leq d_i \\ x_l - x_r \leq -d_i\end{cases}\) 建边。
T3
T4
首先所有被其它区间完全覆盖的区间一定是要删的。
将所有线段左端点第一关键字右端点第二升序排序，考虑 dp。记 \(f_{i,j}\) 表示前 \(i\) 个中选了 \(j\) 个删除，钦定 \(i\) 不删的最长区间覆盖。转移枚举上一个没删的区间。
\[f_{i,j} = \max\limits_{k < i}\{f_{k,j - (i - k - 1)} + r_i - \max(l_i,r_k)\}
\]
显然我们需要分讨后面的 \(\max\)。
-
\(l_i > r_k\)
那么有 \(f_{i,j} = \max\limits_{k<i}\{f_{k,k - (i - j - 1)} + r_i - l_i\}\)，那么我们只需要知道 \(f_{k,k - (i - j - 1)}\) 对于每个 \(i - j - 1\) 的最大值即可。
-
\(l_i < r_k\)
那么有 \(f_{i,j} = \max\limits_{k<i}\{f_{k,k - (i - j - 1)} + r_i - r_k\}\)，同理的我们需要维护 \(f_{k,k - (i-j-1)} - r_k\) 的最大值。
那么只需要单调队列维护第二种情况的同时更新第一种即可。