【CF997E】Good Subsegments

Source and Judge

CF997E

Record

1h

Analysis

请先思考后再展开

$max-min=R-L+1$
$max-min+L-1 \leq R$

和之前维护非负整数的0的数量类似,直接维护最小值及其个数
那么再通过两个单调栈,很容易得出R对应的答案(单次询问log)

本题的关键就在于需要维护好区间的历史答案和,而非单个询问
考虑每次统计R的答案,不是累加答案,而是把左边可行的端点统计贡献数量
(这主要是因为询问的左端点不确定)

那么我们的关键是如何只对最小值进行这个特殊的维护
设每个点向右的贡献为ans[i],那么每次回答询问就是统计区间的这个答案
考虑额外维护一个标记s,表示当前区间所有最小值的ans的加标记
注意到min一定来自两边的至少一侧,每次pushdown就先把lazy下放,然后对min的来源更新s和ans

回答询问就是边搞定上述决策集合,边回答询问就好了

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/1ba5.html
转载请注明出处,谢谢!