P10169 [DTCPC 2024] mex,min,max
Cute_Fish
·
·
题解
好题。注意到 \operatorname{mex} \times \min=0。
考虑容斥:
则答案为 B+C-A。
注意到当 l 固定时，\max，\max-\min 随着 r 增长而不降。于是 A,B 可以二分计算。
处理 C 也不难，维护出每个极短 \operatorname{mex} 区间 [l_0,r_0] 和对应极长区间 [L,R]。则对于任意 l\in[L,l_0],r\in[r_0,R]，\operatorname{mex} 均为定值。
于是，问题转换为对于 l\in[L,l_0],r\in[r_0,R]，有多少 (l,r) 使得 k+c\ge \max_{i=l}^r a_i 其中 c 为定值。
直接算可能会算重，转换为矩阵面积并即可。
极短 $\operatorname{mex}$ 区间个数为 $O(n)$。于是复杂度是 $O(n\log n)$ 常数略大，需要精细实现。