图论解法复杂度为 , 并不会比常规的 最长上升子序列做法 更优, 但是思路可以了解一下 已知, 若 h[i] > h[j] && a[i] > a[j], 那么节点 j 的答案一定至少为节点 i 的答案 +1, 用 dp 转移方程可以表示为 dp[j] = max(dp[j], dp[i]+1), 换句话说, 就是节点 j 的状态由其所有的前置节点确定 自然可以想到, 用一条有向边连接 i -> j, 表示 i 是 j 的 前置节点 , 因此对于一个节点 j, 可以用入度表示 前置节点 的数量, 当我们计算完所有 j 节点的 前置节点 的答案, j 节点的答案...

二分遍历(O(nlog(n*m)) 思路可以参考其他题解, 此题解思路在此基础上进行了一点升级, 使用了数论分块加速 我们观察二分的 check 函数, 其返回值为:  注意到计算  是数论分块的经典问题 因此我们 check 函数的遍历可以使用数论分块思路加速  数论分块思路简单来说, 就是根据  的值给 i 分组, 同组的 i 具有相同的  的结果 因此我们只需要知道每组内有多少个 i, 就能按组得出结果 更详细的内容请去 oi-wiki 上的查看  下面是数论分块一个简单的例子 假设 x = 6    i 1 2 3 4 5 6      6 3 2 1 1 1     可以发现 i =...