题意
-
给定长度为 \(n\) 的数组 \(a_i\)。执行操作 \(m\) 次，每次操作将 \(a_i\) 加上 \(i\)，对于每操作求出，最小的非负整数，使得 \(A\) 不包含它。
-
数据范围：\(1 \le n \le 2 \times 10^5, 1 \le a_i \le 10^9\)。
思路
-
首先当 \(0 \le a_i < n\) 时，\(a_i\) 对答案才会有影响。
-
所以有一种看似暴力的思路：求出 \(i\) 次操作后有哪些数在 \(0 \sim n - 1\) 这范围内，用桶记录一下，枚举每个数，求最小的答案。
-
看似这个会超时，但是实际上是不超时的。因为每次 \(a_i += i\)，所以它满足要求 \(i\) 只会有 \(n / i\) 这么多个，那么一共有 \(\frac{n}{1} + \frac{n}{2} + \dots \frac{n}{n}\) 这么多个数被记录下来，这个就是调和级数，是 \(O(n \log n)\) 的，所以不会炸掉，另外求答案时也只会枚举 \(n \log n\)，所以肯定不会超时。
-
时间复杂度：\(O(n \log n + m)\)，\(m\) 也要枚举一下。