CF809D

传送门

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

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

\(dp[i][j]\) 表示前 \(i\) 个数且第 \(i\) 个数为 \(j\) 的最长上升子序列长度。但是转移方程不好优化，状态表示可以滚动数组压掉一维。

反方向考虑 DP：\(dp[i][j]\) 表示前 \(i\) 个数最长上升子序列长度为 \(j\)，最后一个元素的最小值。同样滚动数组压掉一维。

\(dp[j]=\min(dp[j],l_i)\)，当 \(dp[j-1]<l_i\)

\(dp[j]=\min(dp[j],dp[j-1]+1)\)，当 \(dp[j-1]\in[l_i,r_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 啦！

区间加一就用懒标记的方法。