peltorator

Алгоритм МО с изменениями

Nov 5th, 2018
509
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <map>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <string>
  8. #include <cstring>
  9. #include <set>
  10. #include <queue>
  11. #include <unordered_set>
  12. #include <complex>
  13. #include <unordered_map>
  14. #include <bitset>
  15. #include <ctime>
  16. #include <cassert>
  17.  
  18. #define sz(a) (int)((a).size())
  19.  
  20. using namespace std;
  21.  
  22. typedef long long ll;
  23. typedef long double ld;
  24.  
  25. const int N = 200001;
  26.  
  27. int cnt[N];
  28. int arr[N];
  29. int sz[N];
  30. int ql[N], qr[N];
  31.  
  32. void inc(int n, int d)
  33. {
  34.  //   if (cnt[n] >= 0)
  35.         sz[cnt[n]]--;
  36.     cnt[n] += d;
  37.    // if (cnt[n] >= 0)
  38.         sz[cnt[n]]++;
  39. }
  40.  
  41. int solve()
  42. {
  43.     ios::sync_with_stdio(0);
  44.     int n;
  45.     if (!(cin >> n))
  46.     {
  47.         return 1;
  48.     }
  49.     int m;
  50.     cin >> m;
  51.     vector<int> a(n);
  52.     for (int i = 0; i < n; i++)
  53.         cin >> a[i];
  54.     int timer = -1;
  55.     int query = 0;
  56.     vector<pair<pair<int, int>, pair<int, int> > > q;
  57.     vector<pair<int, int> > change;
  58.     set<int> setik;
  59.     for (int i : a)
  60.         setik.insert(i);
  61.     int B = 47 * 47;
  62.     for (int i = 0; i < m; i++)
  63.     {
  64.         int type;
  65.         cin >> type;
  66.         if (type == 1)
  67.         {
  68.             int l, r;
  69.             cin >> l >> r;
  70.             l--;
  71.           //  r--;
  72.             ql[query] = l;
  73.             qr[query] = r;
  74.             q.push_back({{l / B, r / B}, {timer, query}});
  75.             query++;
  76.         }
  77.         else
  78.         {
  79.             timer++;
  80.             int p, x;
  81.             cin >> p >> x;
  82.             setik.insert(x);
  83.             p--;
  84.             change.push_back({p, x});
  85.         }
  86.     }
  87.     map<int, int> mapa;
  88.     int num = 0;
  89.     for (int i : setik)
  90.     {
  91.         mapa[i] = num++;
  92.     }
  93.     for (int i = 0; i < n; i++)
  94.         a[i] = mapa[a[i]];
  95.     for (int i = 0; i <= timer; i++)
  96.         change[i].second = mapa[change[i].second];
  97.     sort(q.begin(), q.end());
  98.     vector<int> ans(query, 0);
  99.     timer = 1e9;
  100.     int curl, curr;
  101.     for (int i = 0; i < q.size(); i++)
  102.     {
  103.         int ind = q[i].second.second;
  104.         int t = q[i].second.first;
  105.         int l = ql[ind];
  106.         int r = qr[ind];
  107.         if (t < timer)
  108.         {
  109.             for (int i = 0; i < N; i++)
  110.                 cnt[i] = 0;
  111.             for (int i = 0; i < n; i++)
  112.                 arr[i] = a[i];
  113.             for (int i = 0; i < N; i++)
  114.                 sz[i] = 0;
  115.             timer = -1;
  116.             curl = l;
  117.             curr = l;
  118.         }
  119.         while (curl > l)
  120.         {
  121.             curl--;
  122.             inc(arr[curl], 1);
  123.         }
  124.         while (curr < r)
  125.         {
  126.             inc(arr[curr], 1);
  127.             curr++;
  128.         }
  129.         while (curl < l)
  130.         {
  131.             inc(arr[curl], -1);
  132.             curl++;
  133.         }
  134.         while (curr > r)
  135.         {
  136.             curr--;
  137.             inc(arr[curr], -1);
  138.         }
  139.         while (timer < t)
  140.         {
  141.             timer++;
  142.             int pos = change[timer].first;
  143.             if (l <= pos && pos < r)
  144.             {
  145.                 inc(arr[pos], -1);
  146.                 inc(change[timer].second, 1);
  147.             }
  148.             arr[pos] = change[timer].second;
  149.         }
  150.         int j = 0;
  151.         while (sz[j])
  152.             j++;
  153.         ans[ind] = j;
  154.     }
  155.     for (int i : ans)
  156.         cout << i << '\n';
  157.     cout << endl;
  158.     return 0;
  159. }
  160.  
  161. int32_t main()
  162. {
  163.     #ifdef ONPC
  164.         freopen("in.txt", "r", stdin);
  165.     #elif KEK
  166.         freopen("cnt-mex.in", "r", stdin);
  167.         freopen("cnt-mex.out", "w", stdout);
  168.     #endif
  169.     int T = 100;
  170.     //cin >> T;
  171.     for (int i = 1; i <= T; i++)
  172.     {
  173.         #ifdef ONPC
  174.             cout << "Test #" << i << ":\n";
  175.         #endif
  176.         if (solve())
  177.             break;
  178.         #ifdef ONPC
  179.             cerr << "_______________________________________________" << endl;
  180.         #endif
  181.     }
  182.     #ifdef ONPC
  183.         cerr << endl << "finished in " << clock() * 1000LL / CLOCKS_PER_SEC << " ms" << endl;
  184.     #endif
  185.     return 0;
  186. }
RAW Paste Data