CF1436E Complicated Computations
mex的定义是：一个区间中没有出现过的数中最小的整数。
对于一个区间，当正整数x在区间中没有出现过、[1, x - 1]（整数）在区间中全部出现过，那么正整数x就是该区间的mex
正整数x在区间中没有出现过
我们一共有n个数字，所有的数字都不出现一次，就一共有n次的不出现。
x1.......x2.......x3...........................x4（其中x1 = x2 = x3 = x4）若一个区间的mex值是x，那么这样的区间一定在两个x之间。
这样的在两个相同值之间的线段一共有约等于n条（<n）
所以我们现在要枚举区间的mex，从小往大枚举
并且在找到所有与枚举值相同的点，在判断这些值相同的点之间有没有出现过[1, mex - 1]，若是有一个区间满足[1, mex - 1]都出现过，则该mex可以继续往上面加
怎么判断区间l到r之中值域为[1,x]的点都出现过一次呢？
考虑用线段树维护。
我们首先要值域[1,x]，所以线段树上的区间是值域的区间
那么线段树上的值是什么呢，而且还要维护l到r的条件。
我们发现r的条件比较好转换，只需要边添加点，边查询就可以了（这里我们可以不用边枚举mex的值边计算mex是否满足条件，而是先枚举所有的点，找到与前面一个点相同的位置并判断这个区间可不可行，这样也能更好地解释子区间的数量大约是n条了）
那么就是l的值了，还有[1,x]的出现条件
一个很自然的想法是维护[1,x]的出现数量，但是区间的数量并不能反映个体。
那么最大最小值呢？
什么东西的最大最小值才可以反映[1,x]是否全部在[l,r]中出现过，而且还要与l有一定的联系。
坐标
[1,x]中的元素的 最后一个坐标 的 最小值。
最后一个是贪心的思想，最小值是为了通过满足条件，如果最后一个都不能满足条件，那么这个区间的mex一定不是mex，而是[1,mex-1]中的一个数字。
qwq.2023-11-15 20:09:29
标签：Computations,题解,线段,最小值,枚举,Complicated,区间,出现,mex From： https://www.cnblogs.com/ybC202444/p/17834673.html