看到题目很容易想到压位+线段树,但是因为我太懒了这不太好写,我上网查了查发现了另一个很有意思的做法.
loj2554题解
首先注意到给定的区间之间要么不相交,要么嵌套,否则肯定不合法,而且一定有一个覆盖整个序列的区间. 据此我们可以发现区间之间嵌套的关系形成了一个树结构,树中每个点是一个极大的连续的区间. 因此我们只需求出$f _i$表示长为$i+1$的,不存在任何不包含最后一位的连续区间的,排列的个数.
loj2555题解
首先考虑$m=1$的情况,这个时候显然直接二分+按价格贪心就可以了. 如果直接把这个算法应用到原题,复杂度是$\mathcal O(nm\log^2 n)$. 结果我就开始想整体二分,想复杂了.