LG 3246 [HNOI2016]序列

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转设$[l,r]$之间最小值位置为$p$,原数组为$a$那么左端点在$[l,p]$,右端点在$[p,r]$的区间的最小值都是$a[p]$那么这部分的贡献为$a[p] \times (p-l+1) \times (r-p+1)$接下来还有$[l,p-1],[p+1,r]$没有处理设$pre_i$为$i$前第一个比$a[i]$小的数的位置(用单调栈筛出)存在$x$,满足$pre_x=p$设$f[l][r]$表示以$r$为右端点,左端点在$[l,r]$的区间的答案那么$f[l][r]=f[l][pre_r]……