题解：CF2121H Ice Baby

考虑对于每个数，它的选取只有两种情况

1.取$l_i$

2.取和非严格递增子列中上一个数相同的值

设$dp[i]$为最后一个数为$i$时子列的最大长度

用线段树维护这个$dp$数组

每加进来一个数，模拟这两种情况

1：将$l_i$点的值变为$[1,l_i]$区间的最大值再+1

2：使所有$l_i$到$r_i$的值+1

答案统计：取最大值

设$dp_i$为长度为i的子列最后一项的最小值

$dp_i$一定单调不减，所以我们不管下标，直接拿multiset维护整个dp数组，最后dp数组的元素个数就等于最大长度

为方便说明，不妨设$dp[i]-dp[j]$恰好对应对于所有值在$[l_i,r_i]$的dp值

首先，可以在这一位补一个和子列最后一个数相同的数，那么就相当于$dp[i]-dp[j]$转移为了$dp[i + 1]-dp[j + 1]$

需要把原来的$dp[j + 1]$给删了用来“让位”

同时，这一位可以取$l_i$放在$dp[i - 1]$的后面，把$dp[i]$变为$l_i$（因为原来的$dp[i]$比$l_i$大所以这样一定更优）

至此，这一轮的乾坤大挪移就完成了