daily pastebin goal
57%
SHARE
TWEET

Untitled

a guest Mar 25th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <ctime>
  6. #include <random>
  7. #include <map>
  8.  
  9. #define f first
  10. #define s second
  11. #define pb push_back
  12. using namespace std;
  13.  
  14. template<typename T1, typename T2> inline void chkmin(T1 & x, T2 y) {if (x > y) x = y;}
  15. template<typename T1, typename T2> inline void chkmax(T1 & x, T2 y) {if (x < y) x = y;}
  16.  
  17. typedef long long ll;
  18.  
  19. const int MAXN = 1e5 + 1, MAXC = 2e5 + 1, BLOCK = 300;
  20. pair<int, pair<int, int>> chng[MAXN];
  21. int cnt[MAXC], cntofcnt[MAXN], ans[MAXN], a[MAXN];
  22.  
  23. struct req {
  24.     int t, l, r, num;
  25.     req(int _t, int _l, int _r, int _num) {
  26.         t = _t, l = _l, r = _r, num = _num;
  27.     }
  28. };
  29.  
  30. bool cmp(req & a, req & b) {
  31.     int bla = a.t / BLOCK, blb = b.t / BLOCK;
  32.     if (bla != blb) return bla < blb;
  33.     bla = a.l / BLOCK, blb = b.l / BLOCK;
  34.     if (bla != blb) return bla < blb;
  35.     return a.r < b.r;
  36. }
  37.  
  38. void add_el(int x) {
  39.     --cntofcnt[cnt[x]];
  40.     ++cntofcnt[++cnt[x]];
  41. }
  42.  
  43. void del_el(int x) {
  44.     --cntofcnt[cnt[x]];
  45.     ++cntofcnt[--cnt[x]];
  46. }
  47.  
  48. int get_coor(vector<int> & vals, int x) {
  49.     return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
  50. }
  51.  
  52. void change(int l, int r, int pos, int nv) {
  53.     if (l <= pos && pos <= r)
  54.         del_el(a[pos]), add_el(nv);
  55.     a[pos] = nv;
  56. }
  57.  
  58. int get_ans() {
  59.     for (int i = 1; ; ++i)
  60.         if (!cntofcnt[i]) return i;
  61. }
  62.  
  63. int main() {
  64.     ios_base::sync_with_stdio(false);
  65.     cin.tie(0), cout.tie(0);
  66.     // freopen("input.txt", "r", stdin);
  67.     int n, q;
  68.     cin >> n >> q;
  69.     int changes = 0;
  70.     vector<int> vals;
  71.     for (int i = 1; i <= n; ++i) {
  72.         cin >> a[i];
  73.         vals.pb(a[i]);
  74.     }
  75.     vector<req> reqs;
  76.    
  77.     for (int i = 0; i < q; ++i) {
  78.         int t, l, r;
  79.         cin >> t >> l >> r;
  80.         ans[i] = -1;
  81.         if (t == 1)
  82.             reqs.pb(req(changes, l, r, i));
  83.         else {
  84.             chng[changes++] = {l, {a[l], r}};
  85.             vals.pb(r);
  86.             a[l] = r;
  87.         }
  88.     }
  89.     for (int i = changes - 1; i >= 0; --i)
  90.         a[chng[i].f] = chng[i].s.f;
  91.     sort(vals.begin(), vals.end());
  92.     int n1 = unique(vals.begin(), vals.end()) - vals.begin();
  93.     while (vals.size() > n1)
  94.         vals.pop_back();
  95.  
  96.     for (int i = 1; i <= n; ++i) {
  97.         a[i] = get_coor(vals, a[i]);
  98.     }
  99.     for (int i = 0; i < changes; ++i) {
  100.         chng[i].s = {get_coor(vals, chng[i].s.f), get_coor(vals, chng[i].s.s)};
  101.     }
  102.     sort(reqs.begin(), reqs.end(), cmp);
  103.     int l = 1, r = 0, ct = 0;
  104.     for (auto i : reqs) {
  105.  
  106.         while (r < i.r)
  107.             add_el(a[++r]);
  108.         while (r > i.r)
  109.             del_el(a[r--]);
  110.         while (l < i.l)
  111.             del_el(a[l++]);
  112.         while (l > i.l)
  113.             add_el(a[--l]);
  114.         while (ct < i.t) {
  115.             change(l, r, chng[ct].f, chng[ct].s.s);
  116.             ++ct;
  117.         }
  118.         while (ct > i.t) {
  119.             --ct;
  120.             change(l, r, chng[ct].f, chng[ct].s.f);
  121.         }
  122.         ans[i.num] = get_ans();
  123.     }
  124.     for (int i = 0; i < q; ++i) {
  125.         if (ans[i] != -1)
  126.             cout << ans[i] << '\n';
  127.     }
  128.     return 0;
  129. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top