P11325 【MX-S7-T3】「SMOI-R2」Monotonic Queue 笔记

SM 的大神都太强了。

首先，区间肯定相交，因为答案只和队尾弹出有关，并且先动队尾再动队头，所以如果区间不交，把后面的区间的 $l$ 前移，答案一定不劣。

一个 $c_i$ 能够被算进答案，当且仅当存在 $[l_j,r_j]$ 满足 $l_j\le i\wedge nx{t}_i\le r_i$，其中 $nx{t}_i$ 是后面第一个 $>a_i$ 的数。

若 $l_i=l_{i+1}$，则 $[l_{i+1},r_{i+1}]$ 完全可被 $[l_i,r_{i+1}]$ 代替。

结合上面三点，考虑在每个 $l_i=i$ 计算 $c_i$ 会被算进答案的可能。

设 $f_{i,j}$ 表示考虑到前 $i$ 个数，并且 $r_i=j$ 的方案数。

则有 $f_{i,j}=\underset{k=i}{\overset{j}{max}}{f}_{i-1,k}+c_i\times [j\ge nx{t}_i]$。

考虑线段树优化，对 $i$ 这维做扫描线，维护前缀 $max$（显然 $i\ge j$ 的状态是无效状态）。

每次即相当于对 $[nx{t}_i,n]$ 这一段加上 $c_i$。

如果 $c_i$ 是负的话，可能会弄出一段不满足前缀 $max$ 的，找到线段树中开始下降前一个的数（注意不要找到无效状态），对这一段不满足前缀 $max$ 性质的直接覆盖。

我们可以在任意一个地方立正，此时你肯定不能把 $j$ 伸到很远的地方，只能伸到 $i+1$。

所以答案是扫描线每一个时刻，对线段树的 $i+1$ 取 $max$。

还要对原地立正的答案（$0$）取 $max$。

时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。