神奇の性质-526互联

定义对于一个区间 \([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\) 的情况同理，只需固定右端点即可