突然发现自己暑假写过这题。

显然可以考虑动态规划，但不难发现用时间做状态没前途，用站点做状态转移比较困难，而用车次做转移刚刚好。

设 $f_i$ 表示坐上列车 $i$ 的最小烦躁值，因为并没有保证 $x_i<y_i$，所以转移的顺序要按照 $p$ 来排，每次要转移的来源必须满足 $y_j=x_i,q_j\le p_i$。不难完成 $O(n^2)$ 的代码。

考虑优化，注意到转移很像斜率优化，所以使用李超线段树，每次计算完 $f_i$ 后，将 $(q_i,i)$ 放入二叉堆按 $q_i$ 排序。每次转移前，取出二叉堆中所有满足 $q_j\le p_i$ 的 $j$，然后将直线 $j$ 插入第 $y_j$ 个位置的李超树。

李超树动态开点空间复杂度 $O(n)$，时间复杂度 $O(n\log V)$。