问题

给定序列$a_{i}a\_i$和常数$EE$，问有多少种将其划分为若干非空段的方案，使得相邻两段的最小值至少相差$EE$。

题解

设$f_{i}f\_i$表示，已经考虑$a_1\dots a_{i}a\_1\backslash dots\; a\_i$的划分，且$a_{i}a\_i$为其所在段的首个最小值，有多少合法划分方案（$a_{i}a\_i$所在段可能还未闭合）。

考虑对于$ii$，哪些区间$[l,r][l,\; r]$满足$a_{i}a\_i$是首个最小值

用单调栈预处理$ii$左侧第一个$\le a_i\backslash le\; a\_i$的位置$L_{i}L\_i$，以及$ii$右侧第一个的位置$R_{i}R\_i$

则满足$a_{i}a\_i$为其首个最小值

考虑哪些$jj$ () 可以用$f_{j}f\_j$贡献$f_{i}f\_i$

• $a_j\le a_i-Ea\_j\; \backslash le\; a\_i\; -\; E$

• $a_j\ge a_i+Ea\_j\; \backslash ge\; a\_i\; +\; E$

第一类

$a_j\le a_i-Ea\_j\; \backslash le\; a\_i\; -\; E$

考虑$jj$和$ii$之间有多少种可能的断点

依据我们对$ii$成为最小值的区间的观察，断点必须在$L_{i}L\_i$右边

又注意到这些$jj$显然满足$j\le L_{i}j\; \backslash le\; L\_i$

故$(L_i,i](L\_\{i\},\; i]$都可成为$jj$所在段与$ii$所在段的断点

对于一个$jj$，它在$i\in (j,R_j)i\; \backslash in\; (j,\; R\_j)$可能成为一个能对$ii$做贡献的$jj$

使用树状数组，维护对于目前$ii$可贡献的那些$jj$，以$a_{j}a\_j$为下标的$ff$的前缀和

$f_i{\leftarrow }^{+}(i-L_i)\ast bit\mathrm{.}query(a_i-E)f\_i\; \backslash leftarrow^\{+\}\; (i\; -\; L\_i)\; *\; bit.query(a\_i\; -\; E)$

第二类

$a_j\ge a_i+Ea\_j\; \backslash ge\; a\_i\; +\; E$

考虑$jj$和$ii$之间有多少种可能的断点

依据我们对$jj$成为最小值的区间的观察，断点必须在$R_{j}R\_j$左边

又注意到$i\ge R_{j}i\; \backslash ge\; R\_j$

故$(j,R_j](j,\; R\_\{j\}]$都可以成为$jj$所在段和$ii$所在段的断点

$a_{i}a\_i$必须是断点到$ii$这一段的最小值

则$f_{i}f\_i$从第二类$jj$获得的实际贡献$cont{r}_{i}contr\_i$，应为满足要求1.的所有$jj$对其的贡献之和${\sum }_j{f}_j\times (R_j-j)\backslash sum\_j\; f\_j\; \backslash times\; (R\_j\; -\; j)$，减去$cont{r}_{L_i}contr\_\{L\_i\}$

如此一来便能抵消所有$a_{i}a\_i$并非断点到$ii$这一段的最小值的情况下的非法贡献。

计算完$f_{i}f\_i$后，令$cont{r}_k{\leftarrow }^{+}{f}_{i}contr\_k\; \backslash leftarrow^+\; f\_i$ ($k\ge lk\; \backslash ge\; l$)，其中$ll$为最小的满足$l>il\; >\; i$且$a_l\le a_i-Ea\_l\; \backslash le\; a\_i\; -\; E$的下标

同时令$L_j=iL\_j=i$的$jj$的$cont{r}_{i}contr\_i$减去自己的$cont{r}_{i}contr\_i$

$f_i{\leftarrow }^{+}cont{r}_{i}f\_i\; \backslash leftarrow^\{+\}\; contr\_i$

时间复杂度$O(N\log N)O(N\; \backslash log\; N)$

吐槽

这题应该是真正意义的防AK题，于是题面理所应当的用了Chao Man，结果Chao Man就被奶死了。 这里是不是应该放一个：

谢谢大家。