题意: 对单个固定序列多次操作,输出每次操作后的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)。
标签:abc,复杂度,330E,每次,枚举,set,mex From: https://www.cnblogs.com/Fluoresce/p/17894415.html