题解：CF2146E Yet Another MEX Problem

· · 题解

Trick：放宽限制

很经典的Trick，当题目的限制难以计算和维护时，考虑是否存在一种更平凡的维护条件，而能使得题目的限制在这种条件下自然称为最优解。

思考如果只需要维护一个数列的重量，我们用线段树维护对于每个没出现的数，比它大的数有多少个，显然 mex 对应的值会自然地成为其中的最大值。

考虑维护所有以 r 为右端点的子区间中的不存在的数的比它大的数的最大值的最大值，则对于每个数，只有它上一次出现的位置加一，到 r 的这个区间能成为它为最大值的可能区间。因此对所有值，在右端点的值与其相同时将其清零，右端点的值大于其时将其加一即可。