fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define mid (b+e)/2
  3. #define left node<<1
  4. #define right (node<<1)|1
  5. #define mx 100005
  6. using namespace std;
  7.  
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/pb_ds/tree_policy.hpp>
  10. using namespace __gnu_pbds;
  11. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  12. #define ordered_multiset tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update>
  13.  
  14. int arr[mx];
  15. ordered_multiset t[4*mx];
  16. void init(int node, int b, int e)
  17. {
  18.     if(b==e)
  19.     {
  20.         t[node].insert({arr[b], b});
  21.         return;
  22.     }
  23.     init(left,b,mid);
  24.     init(right,mid+1,e);
  25.     for(auto x:t[left]) t[node].insert(x);
  26.     for(auto x:t[right]) t[node].insert(x);
  27. }
  28.  
  29. int query(int node, int b, int e, int i, int j, int x)
  30. {
  31.     // cout<<node<<":"<<b<<":"<<e<<":"<<i<<":"<<j<<"\n";
  32.     if(b>j || e<i) return 0;
  33.     if(i<=b && j>=e){
  34.         // cout<<"===>\n";
  35.         // for(auto [xx, yy]:t[node]) cout<<xx<<":"<<yy<<" "; cout<<"))";
  36.         int ret = t[node].order_of_key({x+1, 0});
  37.         // cout<<node<<":"<<ret<<")";
  38.         return ret;
  39.     }
  40.     return query(left, b, mid, i, j, x) + query(right, mid+1, e, i, j, x);
  41. }
  42.  
  43. void update(int node, int b, int e, int i, int x){
  44.     t[node].erase(t[node].find({arr[i], i}));
  45.     t[node].insert({x, i});
  46.     if(b==e) return;
  47.     if(i<=mid) update(left, b, mid, i, x);
  48.     else update(right, mid+1, e, i, x);
  49. }
  50.  
  51. int main()
  52. {
  53.     ios_base::sync_with_stdio(false);cin.tie(NULL);
  54.     int n, q;
  55.     cin>>n>>q;
  56.     for(int i=1; i<=n; i++) cin>>arr[i];
  57.     init(1, 1, n);
  58.  
  59.     while(q--){
  60.         char c;
  61.         cin>>c;
  62.         if(c=='C'){
  63.             int l, r, x;
  64.             cin>>l>>r>>x;
  65.             cout<<query(1, 1, n, l, r, x)<<"\n";
  66.         } else {
  67.             int i, x;
  68.             cin>>i>>x;
  69.             update(1, 1, n, i, x);
  70.             arr[i]=x;
  71.         }
  72.     }
  73. }
Runtime error #stdin #stdout 0.78s 2095780KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lfWNVt
language:
C++ (gcc 8.3)
created:
2 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!