CF960F

首先，本题的本质是有向图的 LIS 问题，按照题目输入的顺序依次加边，设 \(f_{i,j}\) 表示以 \(i\) 结尾，路径权值的最大值为 \(j\) 的最长链的长度，有状态转移方程 \(f_{i,j}=\max(f_{k,s})+1(k\to i,s<j,val(k\to j)=k)\)，直接转移时间空间复杂度直接爆炸，考虑用动态加点线段树维护 \(f_{i,j}\)，即加入一条 \(i\to j\)，且权值为 \(k\) 的边时，有 \(f_{j,k}=\max_{x=0}^{k-1}(f_{i,x})+1\)，区间查询即可。时间复杂度为 \(O(m\log V)\)。代码。