D

给定两个序列a和b,求有多少区间[l,r]满足a[l,r]\_max == b[l,r]\_min

二分 + RMQ

枚举l,对于每个l,随着r的右移,我们知道a\_max一定是递增的,而b\_min一定是递减的
所以,a\_max - b\_min 是递增的,我们可以通过二分找到a\_max - b\_min = 0的区间(lower_bound 和upper_bound)
区间长度即对答案的贡献

复杂度$O(nlog(n))$

滑窗 单调队列

我们利用单调队列可以表示当前区间[l,r]内的最大值和最小值
r递增,每次若最大值大于最小值,则右移l
然后对于每个区间,若最大值减去最小值恰为0
则这段区间对答案的贡献为 $min(pos_{max},pos_{min}) - l + 1$
即r结尾的最大值减去最小值恰为0的区间个数 ([(l..$min(pos_{max},pos_{min})$),r])

复杂度$O(n)$

扩展

  • 一个序列
  • 最大值与最小值满足某个大小关系

p.s. 都可以用以上方法解决

  • 两个序列的l,r不限制

p.s. 用单调栈预处理出每个值作为最大/最小值的区间向左扩展和向右扩展的长度,区间个数即二者乘起来
考虑到若有相同的值可能会重复计算,所有我们在预处理时
规定向一个方向扩展时严格递增(减),向另一个方向扩展时非严格递增(减)
这个方法非常巧妙

E

给若干区间
求所有的被其中的k个区间覆盖的区间长度(可重复覆盖)

离散化

统计入点和出点,排序,扫描
若区间覆盖次数cnt>=k,则对答案贡献为$C_{cnt}^{k}*len$

复杂度 $O(nlogn + n)$