fork(4) download
copy 
  1. #include<bits/stdc++.h>
  2. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  3. #define ll long long
  4. using namespace std;
  5. #define left(i) (2*i + 1)
  6. #define right(i) (2*i + 2)
  7. #define parent(i) ((i-1)/2)
  8. #include <vector>
  9.  
  10. template<class T>
  11. class SegmentTree
  12. {
  13.     public:
  14.         SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
  15.         SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
  16.         T query(int l, int r);
  17.         void update(int idx, T val);
  18.         //TODO lazy propagation
  19.     private:
  20.         T *tree;
  21.         void buildTree(std::vector<T> data);
  22.         int segTreeSize;
  23.         T valueForExtraNodes;
  24.         T (*combine)(T obj1, T obj2);
  25.         int calculateSize(int n);
  26.         T queryHelper(int l,int r, int st, int ed, int node);
  27. };
  28.  
  29. template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
  30.                                                 T value, T (*combine)(T obj1, T obj2))
  31. {
  32.    this->combine = combine;
  33.    valueForExtraNodes = value;
  34.    segTreeSize = calculateSize(data.size());
  35.    buildTree(data);
  36. }
  37.  
  38. template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
  39.                                             T value, T (*combine)(T obj1, T obj2))
  40. {
  41.    this->combine = combine;
  42.    valueForExtraNodes = value;
  43.    segTreeSize = calculateSize(n);
  44.  
  45.    std::vector<T> data;
  46.    for(int i = 0; i < n; i++)
  47.          data.push_back(ar[i]);
  48.  
  49.    buildTree(data);
  50. }
  51.  
  52.  
  53. template<class T> int SegmentTree<T>::calculateSize(int n)
  54. {
  55.     int pow2 = 1;
  56.     while( pow2 < n)
  57.     {
  58.         pow2 = pow2 << 1;
  59.     }
  60.     return 2*pow2 - 1;
  61. }
  62.  
  63. template<class T> T SegmentTree<T>::query(int l, int r)
  64. {
  65.     int st = 0, ed = segTreeSize/2;
  66.     return queryHelper(l, r, st, ed, 0);
  67. }
  68.  
  69. template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
  70. {
  71.     if( (r < st) || (l > ed) || (l > r) )
  72.         return valueForExtraNodes;
  73.     if(st >= l && ed <= r)
  74.         return tree[node];
  75.     T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
  76.     T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
  77.     return combine(leftVal, rightVal);
  78. }
  79.  
  80. template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
  81. {
  82.    int n = data.size();
  83.    tree = new T[segTreeSize];
  84.    int extraNodes = (segTreeSize/2 + 1) - n;
  85.    for(int i = segTreeSize - 1; i >= 0; i--)
  86.    {
  87.        if(extraNodes>0)
  88.            {
  89.                tree[i] = valueForExtraNodes;
  90.                extraNodes--;
  91.            }
  92.        else if(n>0)
  93.            {
  94.                tree[i] = data[n-1];
  95.                n--;
  96.            }
  97.        else
  98.            tree[i] = combine(tree[left(i)], tree[right(i)]);
  99.    }
  100. }
  101.  
  102. template<class T> void SegmentTree<T>::update(int idx, T val)
  103. {
  104.     int segTreeIdx = (segTreeSize/2) + idx;
  105.     tree[segTreeIdx] = val;
  106.     while(parent(segTreeIdx) >= 0)
  107.     {
  108.         segTreeIdx = parent(segTreeIdx);
  109.         if(right(segTreeIdx) < segTreeSize)
  110.           tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
  111.         if(segTreeIdx == 0)
  112.             break;
  113.     }
  114. }
  115.  
  116. // returns number of employees with salaries between lo and hi
  117. int calc(int lo, int hi, map<int,int>& sal2freq)
  118. {
  119.     int res = 0;
  120.     auto it = sal2freq.lower_bound(lo);
  121.     while(it != sal2freq.end() && it->first <= hi){
  122.         res += it->second;
  123.         it++;
  124.     }
  125.     return res;
  126. }
  127. //returns the bucket number to which x belongs
  128. int bucket_no(int x)
  129. {
  130.     // 1-100 in block 0 but 100/100 = 1
  131.     if(x % 100 == 0)
  132.         x--;
  133.     return (x / 100);
  134. }
  135.  
  136. int sum(int x,int y) { return x+y; }
  137. int main()
  138. {
  139.     fast_io;
  140.     int n,q;
  141.     cin >> n >> q;
  142.  
  143.     vector < int > employee(n);
  144.     vector< int > buckets(10000000, 0);
  145.  
  146.     // salary = key, number of employees with this salary = value
  147.     map < int, int> salary2freq;
  148.  
  149.     for(int  i = 0 ; i < n; i++)
  150.     {
  151.         int salary;
  152.         cin >> salary;
  153.  
  154.         employee[i] = salary;
  155.         salary2freq[salary]++;
  156.  
  157.         buckets[bucket_no(salary)]++;
  158.     }
  159.     SegmentTree < int > rangeSumQueries(buckets, 0, sum);
  160.  
  161.     while(q--)
  162.     {
  163.         char ch;
  164.         cin >> ch;
  165.         if(ch == '!')
  166.         {
  167.             int k,x;
  168.             cin >> k >> x;
  169.             int prev_salary = employee[k-1];
  170.             employee[k-1] = x;
  171.  
  172.             int prev_bucket = bucket_no(prev_salary);
  173.             int new_bucket = bucket_no(x);
  174.  
  175.             buckets[prev_bucket]--;
  176.             buckets[new_bucket]++;
  177.             salary2freq[prev_salary]--;
  178.             salary2freq[x]++;
  179.  
  180.             rangeSumQueries.update(prev_bucket, buckets[prev_bucket]);
  181.             rangeSumQueries.update(new_bucket, buckets[new_bucket]);
  182.         }
  183.         else
  184.         {
  185.             int a,b;
  186.             cin >> a >> b;
  187.  
  188.             int lbucket = bucket_no(a);
  189.             int rbucket = bucket_no(b);
  190.  
  191.             int ans = calc(a, min((lbucket+1)*100, b), salary2freq);
  192.             ans  = ans + ((lbucket!=rbucket) ? calc(max(a, rbucket*100 + 1), b, salary2freq) : 0);
  193.             ans  = ans + rangeSumQueries.query(lbucket+1, rbucket-1);
  194.  
  195.             cout << ans << '\n';
  196.         }
  197.     }
  198.  
  199.     return 0;
  200. }
  201.  
Success #stdin #stdout 0.14s 251480KB
comments (?)
stdin
copy 
5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3
stdout
copy 
3
2
https://ideone.com/zg97c8
language:
C++14 (gcc 8.3)
created:
4 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!