CF809D 题解

· · 个人记录

传送门

平衡树优化神题，完全想不到平衡树能这么用！

一看这题散发着一股 DP 的清香。

反方向考虑 DP：$dp[i][j]$ 表示前 $i$ 个数最长上升子序列长度为 $j$，最后一个元素的最小值。同样滚动数组压掉一维。 $dp[j]=\min(dp[j],l_i)$，当 $dp[j-1]<l_i $dp[j]=dp[j]$，当 $dp[j-1]>r_i$。 一个一个枚举太慢了！我们可以用平衡树维护所有 $dp[j]$。而且我们惊喜地发现 $dp[]$ 存在单调性！$dp[j]<dp[j+1]$，所以我们按照编号排序和按照值排序是一样的。 **考虑每一个转移方程的影响，我们从整体来观察，而不是注意每一个 $dp[j]$ 是否要转移。** 第一个转移方程，在扫完 $dp[1]\sim dp[n]$ 之后，发现其实 $dp[j]<l$ 的 $dp$ 不会变化，而只有 $dp[j-1]<l,dp[j]> l$ 的交界点才会发生变化。 （一开始就小于 $l$，与 $l$ 取 $\min$ 当然不会变化。交界点更新完之后，更新的值至少是 $l$，也不会发生连锁反应，即不会交界点更新之后，更新的数又用第一条转移方程更新后面的。） 于是我们直接在平衡树上插入 $l_i$。（**注意不是把小于 $l_i$ 的最大数的后继变成 $l_i$，因为我们还需要用这个后继更新其他的 dp 值**） 第二个转移方程：相当于把所有 $dp[j]\in[l_i,r_i)$ 的都加一，然后 $dp[j+1]\leftarrow dp[j]$。 这第二个转移方程，会把 $\ge r_i$ 且最小的 $dp$ 值挤掉，替换成 $<r_i$ 且最大的 $dp$ 值加一。所以我们直接删掉 $\ge r_i$ 且最小的 $dp$ 值就行。同时上面插入了一个 $l_i$，第二个转移方程都是 $>l_i$ 的，刚好满足 $dp[j+1]\leftarrow dp[j]$ 的需求。 总结一下： 1. 把所有 $\in[l_i,r_i)$ 的都加一。 2. 插入 $l_i$，注意这里顺序不能搞反，不然这个 $l_i$ 会算进 $\in[l_i,r_i)$ 的里面。 而且我们发现，本来应该删除 $\ge l_i$ 的最小值，再插入 $l_i$ 的（变成 $l_i$），但是因为 $\in[l_i,r_i)$ 的都加一了，所以不用再删除 $\ge l_i$ 的最小值。 3. 删除 $\ge r_i$ 的最小值。 最后的答案就是平衡树的大小。 看到这么多的区间操作，当然是用可爱的 FHQ_Treap 啦！ 区间加一就用懒标记的方法。