CF2146E Yet Another MEX Problem 题解

· · 题解

题目大意

给定一个数组 a，定义“权重”为大于该它子数组 MEX 值的元素个数。对于 [1,n] 内的每个右端点 i，我们需要找到以 i 结尾的所有子数组的最大权重。

思路

我们不难发现，对于固定的右端点 r，当左端点 l 向左移动时，子数组的 MEX 值单调不减。我们观察到，一个值为 v 的元素会对所有 MEX 值小于 v 的情况贡献 1 的权重，而当 v 出现在子数组中时，MEX 值不可能等于 v。

我们遍历每个右端点，首先将位置 a_i +1 的权重清零，然后将区间 [1,a_i ] 的权重 +1（因为 a_i 对所有小于它自身的 MEX 值有贡献），最后查询以 i 为结尾的子数组的最大权重。

而本题数据范围为 1\leq n\leq 3\times 10^5，显然暴力过不去。这时候我们仔细想想需要维护的信息：区间修改、单点修改和区间最大值。所以我们可以用线段树来优化！

时间复杂度：O(n \log n)。