Codeforces809D题解:
题解:
- $dp[i]$表示长度为$i$的序列最后一个数的最小值。
- 考虑转移时加入一段区间$[l,r]$。
- 对于最大的满足$dp[i]<l$的位置:
- 因为$dp[i+1]>=l$,所以转移可以变为直接赋值(一定发生)。
- 对于最大的满足$dp[j]<r$的位置:
- 显然$dp$数组严格单调递增,即$dp[i+1]>=dp[i]+1$,所以上述转移必定发生。
- 所以我们可以通过一颗非旋转$treap$维护$dp$数组。
- 每次删去$dp[j+1]$这个节点,对于$dp[i+1]-dp[j]$这段$dp$区间整体$+1$并右移,再在原来的$dp[i+1]$前加入一个新的$dp[i+1]=l$的节点。
- 这些操作都可以通过$split,merge$较为简单地实现。
代码:
1 |
|