fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. using namespace __gnu_pbds;
  8.  
  9. template <class T>
  10. using orderStaticTree =
  11.     tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  12.  
  13. #define ll long long
  14. #define saleh ios_base::sync_with_stdio(false); cin.tie(nullptr);
  15.  
  16. const int MX = 2e5 + 100;
  17. int n, q;
  18.  
  19. vector<orderStaticTree<pair<int, int>>> bit(MX);
  20.  
  21. void add(int ind, int val, int id) {
  22.     for (; ind <= n; ind += (ind & (-ind))) {
  23.         bit[ind].insert({val, id});
  24.     }
  25. }
  26.  
  27. void remo(int ind, int val, int id) {
  28.     for (; ind <= n; ind += (ind & (-ind))) {
  29.         bit[ind].erase({val, id});
  30.     }
  31. }
  32.  
  33. int range(int mini, int maxi) {
  34.     int ind = n;
  35.     int ans = 0;
  36.     for (; ind > 0; ind -= (ind & (-ind))) {
  37.         ans += bit[ind].order_of_key({maxi + 1, 0}) - bit[ind].order_of_key({mini, 0});
  38.     }
  39.     return ans;
  40. }
  41.  
  42. int main() {
  43.     saleh;
  44.     cin >> n >> q;
  45.     vector<int> v(n + 1);
  46.     for (int i = 1; i <= n; i++) {
  47.         cin >> v[i];
  48.     }
  49.     for (int i = 1; i <= n; i++) {
  50.         add(i, v[i], i);
  51.     }
  52.  
  53.     while (q--) {
  54.         char op;
  55.         cin >> op;
  56.  
  57.         if (op == '?') {
  58.             int mini, maxi;
  59.             cin >> mini >> maxi;
  60.             cout << range(mini, maxi) << endl;
  61.         } else {
  62.             int ind, val;
  63.             cin >> ind >> val;
  64.             remo(ind, v[ind], ind);
  65.             add(ind, val, ind);
  66.             v[ind] = val;
  67.         }
  68.     }
  69.  
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.03s 21868KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ehPD6n
language:
C++ (gcc 8.3)
created:
10 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!