fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define pii pair<int, int>
  6. #define f first
  7. #define s second
  8. #define mp make_pair
  9.  
  10.  
  11. map<int, int> valtoID;
  12. pair<int, pii> queries[(int)2e5+5];
  13. int arr[(int)2e5+5];
  14.  
  15. ll fwt[(int)1e6];
  16. ll sum(int i)
  17. {
  18.     ll sum = 0;
  19.     while(i > 0){
  20.         sum += fwt[i];
  21.         i -= (i & -i);  //least important bit
  22.     }
  23.     return sum;
  24. }
  25. ll query(int a, int b)
  26. {
  27.     return sum(b) - sum(a - 1);
  28. }
  29. void update(int i, ll v)
  30. {
  31.     while(i > 0 && i < 1e6){
  32.         fwt[i] += v;
  33.         i += (i & -i);
  34.     }
  35. }
  36.  
  37. int main() {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(NULL);
  40.  
  41.     int n, q;
  42.     cin >> n >> q;
  43.     for(int i = 0; i < n; i++){
  44.         cin >> arr[i];
  45.         valtoID[arr[i]] = 0;
  46.     }
  47.     for(int i = 0; i < q; i++){
  48.         char t; int l, r, type; cin >> t >> l >> r;
  49.         valtoID[r] = 0;
  50.         if(t == '?'){
  51.             type = 2;
  52.         }
  53.         else{
  54.             type = 1;
  55.             valtoID[l] = 0;
  56.         }
  57.         queries[i] = mp(type, mp(l, r));
  58.     }
  59.     int ID = 1;
  60.     for(auto &t : valtoID){
  61.         t.s = ID++;
  62.     }
  63.  
  64.     for(int i = 0; i < n; i++){
  65.         arr[i] = valtoID[arr[i]];
  66.         update(arr[i], 1);
  67.     }
  68.     for(int i = 0; i < q; i++){
  69.     	int type = queries[i].f;
  70.         if(type == 1){
  71.             update(arr[queries[i].s.f - 1], -1);
  72.             int r = valtoID[queries[i].s.s];
  73.             arr[queries[i].s.f - 1] = r;
  74.             update(r, 1);
  75.         }
  76.         else{
  77.             int l = valtoID[queries[i].s.f];
  78.             int r = valtoID[queries[i].s.s];
  79.             cout << query(l, r) << endl;
  80.         }
  81.     }
  82.  
  83.     return 0;
  84. }
Success #stdin #stdout 0s 4544KB
comments (?)
stdin
copy 
5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3
stdout
copy 
3
2
https://ideone.com/J0ANQd
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!