fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, _n, q;
  4. int a[200005];
  5. int st[4 * 800005];
  6. vector <int> vt;
  7. unordered_map <int, int> h;
  8.  
  9. struct ZATA {
  10.     char d;
  11.     int l, r;
  12. } ques[200005];
  13.  
  14. void upd(int id, int l, int r, int pos, int val) {
  15.     if (l > pos || r < pos) return;
  16.     if (l == r) {
  17.         st[id] += val;
  18.         return;
  19.     }
  20.     int mid = (l + r) / 2;
  21.     upd(id * 2, l, mid, pos, val);
  22.     upd(id * 2 + 1, mid + 1, r, pos, val);
  23.     st[id] = st[id * 2] + st[id * 2 + 1];
  24. }
  25.  
  26. int get(int id, int l, int r, int u, int v) {
  27.     if (l > v || r < u) return 0;
  28.     if (l >= u && r <= v) return st[id];
  29.     int mid = (l + r) / 2;
  30.     return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
  31. }
  32.  
  33. main() {
  34.     ios_base::sync_with_stdio(false);
  35.     cin.tie(0); cout.tie(0);
  36.     cin >> n >> q;
  37.     for (int i = 1; i <= n; i++) {
  38.         cin >> a[i];
  39.         vt.push_back(a[i]);
  40.     }
  41.     for (int i = 1; i <= q; i++) {
  42.         cin >> ques[i].d >> ques[i].l >> ques[i].r;
  43.         if (ques[i].d == '!') {
  44.             vt.push_back(ques[i].r);
  45.         } else {
  46.             vt.push_back(ques[i].l);
  47.             vt.push_back(ques[i].r);
  48.         }
  49.     }
  50.  
  51.     sort(vt.begin(), vt.end());
  52.     vt.erase(unique(vt.begin(), vt.end()), vt.end());
  53.     _n = vt.size();
  54.     for (int j = 0; j < _n; j++) h[vt[j]] = j + 1;
  55.     for (int i = 1; i <= n; i++) {
  56.         a[i] = h[a[i]];
  57.         upd(1, 1, _n, a[i], 1);
  58.     }
  59.  
  60.     for (int i = 1; i <= q; i++) {
  61.         if (ques[i].d == '!') {
  62.             int k = ques[i].l;
  63.             int x = h[ques[i].r];
  64.             upd(1, 1, _n, a[k], -1);
  65.             a[k] = x;
  66.             upd(1, 1, _n, x, 1);
  67.         } else {
  68.             int l = h[ques[i].l];
  69.             int r = h[ques[i].r];
  70.  
  71.             cout << get(1, 1, _n, l, r) << '\n';
  72.  
  73.         }
  74.     }
  75.  
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0s 5536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xdMP5F
language:
C++14 (gcc 8.3)
created:
1 day 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!