题解

kczno1 2018-05-10 15:54:15 2018-05-10 16:31:05

询问一个区间 [l,r] 时,

先求出区间最小值的位置 pos

然后将子区间分成3类:

(1) 跨过 pos

(2) [l,pos-1] 的子区间

(3) [pos+1,r] 的子区间

(1) 直接算, (2),(3) 是本质一样的,下面以 (2) 为例分析。

考虑用 [l,n] 的答案减去 [pos,n] 的答案,那么多算的子区间就是所有左端点在 [l,pos-1] ,右端点在 [pos,n] 的区间

由于 a[pos] a[l..pos-1] 都要小,所以子区间的最小值跟 [l,pos-1] 是无关的

答案实际上就是 \sum_{i=pos}^{n} \min a[pos..i] (记做 suf(pos) )乘上 pos-l

suf(pos) 是可以单调栈预处理的,前面提到的 [pos,n] 的答案也只用对 suf(pos) 求个后缀和就可以得到。

于是问题只剩下 rmq

在询问随机的情况下,可以通过分块来做到 O(n)-O(1) rmq

当询问区间跨过多个块时,预处理块内前后缀答案,块间 ST 表即可 O(1)

当询问区间落在一个块内时,直接暴力。

于是这题可以 O(n+m) 解决,常数不大,代码简单。

参考资料:

https://mogicianevian.github.io/2018/03/18/HNOI-2016-序列(RMQ-单调栈)/

https://www.luogu.org/problemnew/show/P3793

共 3 条回复

kczno1

非常抱歉,已修改题面。。

kczno1

好像是诶,出锅了。。

SHENZHEBEI

这题标程lastAns似乎会爆long long