ABC 272 E - Add and Mex(数学&mex)

显然[0,n][0,n][0,n]的数才有意义。

对于i=1i=1i=1，显然有意义的数最多ni\dfrac{n}{i}in​个。

求和一下最多nlog⁡nn\log nnlogn个有意义的数，考虑开mmm个vector存每轮有意义的数。

然后暴力找即可，因为这些有意的数是不同的，所以暴力最多找一次O(n)O(n)O(n)找满，然后后面都是O(1)O(1)O(1)。

所以总复杂度；O(nlog⁡n)O(n\log n)O(nlogn)

#include 
using namespace std;int main() {int n, m;cin >> n >> m;vector a(n);for(auto &v : a) cin >> v;vector> vals(m + 1);for(int i = 0; i < n; i++) {if(a[i] >= n) continue;int l = (a[i] >= 0 ? 1 : (-a[i] + i) / (i + 1));int r = min(m + 1, (n - a[i] + i) / (i + 1));for(int j = l; j < r; j++) {vals[j].push_back(a[i] + (i + 1) * j);}}for(int i = 1; i <= m; i++) {int sz = vals[i].size();vector exi(sz + 1);for(auto v : vals[i]) {if(v < sz) exi[v] = true;}int res = 0;while(exi[res]) res++;cout << res << endl;}
}