题意
-
给定长度为 \(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\) 也要枚举一下。