fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define bolt_io ios_base::sync_with_stdio(0), cin.tie(0)
  5.  
  6. const int N = 6e5 + 5;
  7. int n, q, uc, n_, ic, st[4 * N], a[N], b[N];
  8. vector<tuple<char, int, int>> vp;
  9. map<int, int> mp;
  10.  
  11. void f1(int sti, int ll, int rr, int ix, int v)
  12. {
  13.     if (ll == rr)
  14.         st[sti] += v;
  15.     else
  16.     {
  17.         int m = (ll + rr) >> 1;
  18.         if (ix <= m)
  19.             f1(2 * sti + 1, ll, m, ix, v);
  20.         else
  21.             f1(2 * sti + 2, m + 1, rr, ix, v);
  22.  
  23.         st[sti] += v;
  24.     }
  25. }
  26.  
  27. int f2(int sti, int ll, int rr, int lq, int rq)
  28. {
  29.     if (rq < ll || rr < lq)
  30.         return 0;
  31.     else if (lq <= ll && rr <= rq)
  32.         return st[sti];
  33.     else
  34.     {
  35.         int m = (ll + rr) >> 1;
  36.         return f2(2 * sti + 1, ll, m, lq, rq) + f2(2 * sti + 2, m + 1, rr, lq, rq);
  37.     }
  38. }
  39.  
  40. signed main()
  41. {
  42.     bolt_io;
  43.     cin >> n >> q;
  44.     for (int i = 0; i < n; i++)
  45.         cin >> a[ic], ic++;
  46.  
  47.     vp.resize(q);
  48.     for (int i = 0; i < q; i++)
  49.     {
  50.         char ch;
  51.         int x, y;
  52.         cin >> ch >> x >> y;
  53.         vp[i] = {ch, x, y};
  54.  
  55.         if (ch == '!')
  56.             a[ic] = y, ic++;
  57.         else
  58.             a[ic] = x, a[ic + 1] = y, ic += 2;
  59.     }
  60.  
  61.     for (int i = 0; i < n; i++)
  62.         b[i] = a[i];
  63.  
  64.     sort(a, a + ic);
  65.     mp[a[0]] = 0;
  66.  
  67.     for (int i = 1; i < ic; i++)
  68.         if (a[i] != a[i - 1])
  69.             mp[a[i]] = mp[a[i - 1]] + 1;
  70.  
  71.     uc = mp.size();
  72.     n_ = 1 << (__lg(uc) + 1);
  73.     if ((uc & (uc - 1)) == 0)
  74.         n_ >>= 1;
  75.  
  76.     for (int i = 0; i < n; i++)
  77.         f1(0, 0, n_ - 1, mp[b[i]], +1);
  78.  
  79.     for (tuple<char, int, int> entry : vp)
  80.     {
  81.         if (get<0>(entry) == '!')
  82.         {
  83.             f1(0, 0, n_ - 1, mp[b[get<1>(entry)] - 1], -1);
  84.             b[get<1>(entry) - 1] = get<2>(entry);
  85.             f1(0, 0, n_ - 1, mp[b[get<1>(entry) - 1]], +1);
  86.         }
  87.         else
  88.         {
  89.             cout << f2(0, 0, n_ - 1, mp[get<1>(entry)], mp[get<2>(entry)]) << ' ';
  90.         }
  91.     }
  92.  
  93.     return 0;
  94. }
Success #stdin #stdout 0.01s 5408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SDqjOP
language:
C++14 (gcc 8.3)
created:
2 years 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!