Codeforces|Codeforces940F Machine Learning (带修莫队) 莫队算法|算法|数据结构|Code

题目链接: Machine Learning 大致题意给定一个长度为 n n n的序列, 第 i i i个元素为 w i w_i wi?.
有两种操作:
1 l r 定义 c i c_i ci?为出现次数为 i i i次的数字个数. 查询 [ l , r ] [l, r] [l,r]的 m e x ( { c 0 , c 1 , . . , c 1 0 9 } ) mex(\{ c_0, c_1, .., c_{10^9}\}) mex({c0?,c1?,..,c109?}).
2 a c 把序列 a a a位置的数字修改为 c c c.
解题思路带修莫队这不是带修莫队裸题吗?
【Codeforces|Codeforces940F Machine Learning (带修莫队)】我们考虑开一个桶统计每个数值出现的次数, 以及出现次数为 x x x的数值个数.
我们通过莫队来维护区间 [ l , r ] [l, r] [l,r]的信息.
考虑到答案查询, 最开始做题的时候我用了值域分块, 由于需要维护一个值域块, 复杂度比别人高了一倍.
后来看到网上大佬们的代码, 都是直接从 1 1 1开始暴力求解的. 于是想了一下, 这样确实是可行的.

考虑到 m e x mex mex最大其实只有 n \sqrt{n} n ?.
因为 1 + 2 + 3 + . . . + n = n × ( n ? 1 ) 2 1 + 2 + 3 + ... + n = \frac{n \times (n - 1)}{2} 1+2+3+...+n=2n×(n?1)?

AC代码

#include #define rep(i, n) for (int i = 1; i <= (n); ++i) using namespace std; typedef long long ll; const int N = 1E5 + 10; int B; vector v(1, -0x3f3f3f3f); int find(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); }int w[N]; pair change[N]; struct mo { int l, r, t, id; bool operator< (const mo& T) const { if (l / B != T.l / B) return l < T.l; if (r / B != T.r / B) return r < T.r; return t < T.t; } }; vector area; int res[N]; int L = 1, R = 0, T = 0; int cou[N << 1], num[N]; void add(int c) { --num[cou[c]], ++num[++cou[c]]; } void sub(int c) { --num[cou[c]], ++num[--cou[c]]; } void modify(int t) { auto& [a, c] = change[t]; if (L <= a and R >= a) { sub(w[a]), add(c); } swap(w[a], c); } int ask() { int res = 1; while (num[res]) res++; return res; }int main() { int n, m; cin >> n >> m; B = pow(n, 2.0 / 3); rep(i, n) scanf("%d", &w[i]), v.push_back(w[i]); int version = 0; rep(i, m) { int tp; scanf("%d", &tp); if (tp == 1) { int l, r; scanf("%d %d", &l, &r); area.push_back({ l, r, version, i }); } else { int a, c; scanf("%d %d", &a, &c); change[++version] = { a, c }; v.push_back(c); } } sort(area.begin(), area.end()); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); rep(i, n) w[i] = find(w[i]); rep(i, version) change[i].second = find(change[i].second); for (auto& [l, r, t, id] : area) { while (l < L) add(w[--L]); while (r > R) add(w[++R]); while (L < l) sub(w[L++]); while (R > r) sub(w[R--]); while (t < T) modify(T--); while (T < t) modify(++T); res[id] = ask(); } rep(i, m) if (res[i]) printf("%d\n", res[i]); return 0; }

END