abc 330E mex

发布时间 2023-12-11 14:57:09作者: Fluoresce

题意: 对单个固定序列多次操作,输出每次操作后的mex函数值。

E - Mex and Update (atcoder.jp)

不能用博弈论求sg函数那种直接枚举(TLE),因为最差可能达到O(n2),就算每次基于上一次的mex来剪枝也会被卡到这个复杂度,因为每次都只能线性枚举,所以这个方法不合适。

因为mex可能取值的情况最多不超过n+1个,所以可以使用stl中的set,来枚举没有在0~n出现的数字,这样做的好处是每次都可以O(1)的找到对应的数(set的第一个元素),并且维护这个单调递增的序列每次只需要O(logn)的复杂度,总的来说就是O(nlogn)。