fork download
copy 
  1.  
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define endl "\n"
  7. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
  8.  
  9. #define F first
  10. #define S second
  11.  
  12. #define rep(i,x,n) for(int i = x; i < n; i++)
  13.  
  14.  
  15. const int N = 2e5 + 5, SQ = 3500;
  16. struct query {
  17. 	  int l, r, idx, uIdx;
  18. 	  bool operator<(const query& other) const{
  19. 	    if (l / SQ != other.l / SQ)
  20. 	      return l / SQ < other.l / SQ;
  21. 	    if (r / SQ != other.r / SQ)
  22. 	      return r / SQ < other.r / SQ;
  23. 	    return uIdx < other.uIdx;
  24. 	  }
  25. 	};
  26. struct update {
  27. 	  int idx, val, old;
  28. };
  29. int a[N], ans[N], frq[N], cnt[N];
  30. void add(int idx) {
  31.     cnt[frq[a[idx]]]--;  // decrease count of previous frequency
  32.     frq[a[idx]]++;
  33.     cnt[frq[a[idx]]]++;  // increase count of new frequency
  34. }
  35.  
  36. void remove(int idx) {
  37.     cnt[frq[a[idx]]]--;
  38.     frq[a[idx]]--;
  39.     cnt[frq[a[idx]]]++;
  40. }
  41. void upd(update& u, int l, int r) {
  42.   if (u.idx >= l && u.idx <= r)
  43.     remove(u.idx);
  44.   a[u.idx] = u.val;
  45.   if (u.idx >= l && u.idx <= r)
  46.     add(u.idx);
  47. }
  48. void cancel(update& u, int l, int r) {
  49.   if (u.idx >= l && u.idx <= r) remove(u.idx);
  50.   a[u.idx] = u.old;
  51.   if (u.idx >= l && u.idx <= r) add(u.idx);
  52. }
  53. void mo(vector<query>& v, vector<update>& u) {
  54.   int l = 0, r = -1;
  55.   int cur = 0;
  56.   for (auto& q : v) {
  57.     while (cur < q.uIdx)
  58.       upd(u[cur++], l, r);
  59.     while (cur > q.uIdx)
  60.       cancel(u[--cur], l, r);
  61.     while (r < q.r) add(++r);
  62.     while (l > q.l) add(--l);
  63.     while (r > q.r) remove(r--);
  64.     while (l < q.l) remove(l++);
  65.     while (cnt[ans[q.idx]]) ans[q.idx]++;
  66.   }
  67. }
  68.  
  69.  
  70.  
  71. int main() {
  72.  
  73.     a[0] = 1; a[1] = 1; a[2] = 1; a[3] = 3; a[4] = 3; a[5] = 3; a[6] = 1;
  74.  
  75.     vector<query> queries = {
  76.         {1, 3, 0, 0},  // query 0, range [1,3], before 0 updates
  77.         {0, 6, 1, 1},  // query 1, range [0,6], after 1 update
  78.     };
  79.  
  80.     vector<update> updates = {
  81.         {2, 2, a[2]}  // update index 2 to value 2
  82.     };
  83.  
  84.     mo(queries, updates);
  85.  
  86.     cout << ans[0] << " " << ans[1];  // prints answers
  87. }
Success #stdin #stdout 0.01s 5652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3 2
https://ideone.com/5XRdfi
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!