Add and Mex（时间复杂度，枚举）

题意

给定一个包含\(N\)个元素的序列\(A = (A_1, \dots, A_N)\)。

下述操作执行\(M\)次：对于每个\(i, (1 \leq i \leq N)\)，将\(A_i\)加上\(i\)。然后求序列的mex。

题目链接：https://atcoder.jp/contests/abc272/tasks/abc272_e

数据范围

\(1 \leq N, M \leq 2 \times 10^5\)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int N = 200010;

int n, m;
int a[N];
vector<int> f[N];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++) {
        if(a[i] >= n) continue;
        int l = (a[i] >= 0 ? 1 : (-a[i] - 1) / i + 1);
        int r = min(m + 1, (n - a[i] - 1) / i + 1);
        for(int j = l; j < r; j ++) {
            f[j].push_back(a[i] + i * j);
        }
    }
    for(int i = 1; i <= m; i ++) {
        int nx = 0;
        sort(f[i].begin(), f[i].end());
        f[i].erase(unique(f[i].begin(), f[i].end()), f[i].end());
        if(!f[i].size()) {
            printf("0\n");
            continue;
        }
        bool flag = false;
        for(auto p : f[i]) {
            if(p != nx) {
                flag = true;
                printf("%d\n", nx);
                break;
            }
            nx ++;
        }
        if(!flag) printf("%d\n", nx);
    }
    return 0;
}