ABC 272E - Add and Mex（MEX，调和级数）

https://atcoder.jp/contests/abc272/tasks/abc272_e

题意
给定了一个长度为 n 的序列 a[]。
执行如下操作 m 次：

• 对于每个位置 i，令 a[i] += i；
• 输入改变之后数组的 MEX 值（首个未出现的非负整数）。

$1\le N,M\le 2\times 10^5$
$-10^9\le A_i\le 10^9$

思路
场上想的时候，无论是正着来还是倒着来，对每次操作都无法避免把数组所有的位置都遍历一遍。于是就陷入了僵局。

首先需要知道一个小性质：如果要求一个长度为 n 的数组的 MEX，那么数组中 小于0的数 和 大于n的数 是对答案没有任何影响的。

然后这个题目中，位置 i 上的值 a[i] 每次加上 i，那么 a[i] 就最多只有 $\lfloor \frac{n}{i}\rfloor$ 个操作之后的数是对答案有贡献的。

对于每个位置 1，2，3，4，5…，分别有 $\lfloor \frac{n}{1}\rfloor$，$\lfloor \frac{n}{2}\rfloor$，$\lfloor \frac{n}{3}\rfloor$，$\lfloor \frac{n}{4}\rfloor$，$\lfloor \frac{n}{5}\rfloor$… 个有贡献的数，是调和级数。

那么就可以 O(nlogn) 预处理出来每个位置在哪些询问里贡献数字，存在那个询问的 vector 中。
对于每个询问，只要求 vector 中所有数的 MEX 即可。

因为每次都加上 i，就算有一个询问中出现了 0-n，加过之后下一个询问就没有了，所以一个询问中能从 0 开始连续的数字长度其实是很小的，那么直接从 0 开始枚举看哪个数不存在即可。

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
set<int> st[N];

signed main(){
	Ios;
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
		int idx = 0;
		if(a[i] < 0) //一开始可能小于0，需要|ai|/i次操作才能增上去
		{
			int cha = -a[i];
			idx += cha/i;
			a[i] += idx * i;
		}
		if(a[i] == 0 && idx <= m) st[idx].insert(0); 
		while(idx + 1 <= m && a[i] + i <= n)
		{
			idx ++;
			a[i] += i;
			st[idx].insert(a[i]);
		}
	}
	
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
		{
			if(!st[i].count(j))
			{
				cout << j << endl;
				break;
			}
		}
	}
	
	return 0;
}

1，2，3，4，5 每次按这样的步数跳着走，要能想到调和级数！！

遇见调和级数几次了！

对于 小于0 和 大于n 的数字对一个数组的 MEX 没有贡献就不用管，只找出那些有贡献的数，一个数每次加上 i，就只有在 n/i 个询问里有贡献，然后调和级数预处理出来放到那个询问的vector里，还是挺不好想的。

以后看到每次增加 1，2，3，4 … 要能想到调和级数。