- 定义对于一个区间 \([l,r]\) 中不存在 \(l \leq l' \leq r' \leq r\) 满足 \(mex(l,r) = mex(l',r')\) ,则称这个区间为“好的区间” 。好的区间只有 \(O(n)\) 个。
证明:不妨设 \(a_l > a_r\) ,显然有 \(a_l < mex(l,r)\) ,假设对于以 \(l\) 为左端点存在另一个好的区间 \([l,r']\) 满足 \(r' > r\) 且 \(a_l > a_{r'}\) ,则 \(a_{r'} < a_l < mex(l,r)\) ,说明 \(a_{r'}\) 一定已经在 \([l,r]\) 中出现过了,一定不会产生有效贡献,因此 \([l,r']\) 不可能是一个“好的区间”
而对于 \(a_l < a_r\) 的情况同理,只需固定右端点即可