fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4.  
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. int v[100005];
  9. const int BUCKET_SIZE = 320;
  10.  
  11. int S[BUCKET_SIZE][BUCKET_SIZE];
  12.  
  13. vector<int> M[BUCKET_SIZE];
  14.  
  15. int n;
  16.  
  17. void build(){
  18.  
  19.     for(int i = 0; i < n ; i += BUCKET_SIZE){
  20.         int inicio = i;
  21.         int fin = min(i + BUCKET_SIZE - 1, n - 1);
  22.  
  23.         vector<int> aux;
  24.         for(int j = inicio; j <= fin; j++){
  25.             aux.push_back(v[j]);
  26.         }
  27.  
  28.         sort(aux.begin(), aux.end());
  29.  
  30.         for(int j = 0, pos = 0; j < aux.size(); pos++){
  31.             int valor = aux[j];
  32.             int e = j;
  33.  
  34.             M[i/BUCKET_SIZE].push_back(valor);
  35.  
  36.             while(aux[e] == valor && e < aux.size()){
  37.                 e++;
  38.             }
  39.  
  40.             S[i/BUCKET_SIZE][pos] += e - j;
  41.             if(pos) S[i/BUCKET_SIZE][pos] += S[i/BUCKET_SIZE][pos-1];
  42.  
  43.             j  = e;
  44.  
  45.         }
  46.  
  47.  
  48.     }
  49. }
  50.  
  51. void update(int pos, int val){
  52.  
  53.     v[pos] = val;
  54.     int bucket = pos / BUCKET_SIZE;
  55.  
  56.     int inicio = BUCKET_SIZE * bucket;
  57.     int fin = min(inicio + BUCKET_SIZE - 1, n - 1);
  58.  
  59.     vector<int> aux;
  60.     for(int j = inicio; j <= fin; j++){
  61.         aux.push_back(v[j]);
  62.     }
  63.  
  64.     sort(aux.begin(), aux.end());
  65.  
  66.     M[bucket].clear();
  67.     for(int j = 0, pos = 0; j < aux.size(); pos++){
  68.         int valor = aux[j];
  69.         int e = j;
  70.  
  71.         M[bucket].push_back(valor);
  72.  
  73.         while(aux[e] == valor && e < aux.size()){
  74.             e++;
  75.         }
  76.  
  77.         S[bucket][pos] = e - j;
  78.         if(pos) S[bucket][pos] += S[bucket][pos-1];
  79.         j  = e;
  80.  
  81.     }
  82.  
  83. }
  84.  
  85. int query(int l, int r, int x){
  86.  
  87.     int bucket = l / BUCKET_SIZE;
  88.     int ans = 0;
  89.     for(int i = bucket; ; i++){
  90.  
  91.         int inicio = i  * BUCKET_SIZE;
  92.         int fin = min(i * BUCKET_SIZE - 1, n - 1);
  93.         if(inicio > r) break;
  94.  
  95.         int p = lower_bound( M[i].begin(), M[i].end(), x) - M[i].begin();
  96.  
  97.         if(p == M[i].size()) p--;
  98.  
  99.         if(M[i][p] > x) p--;
  100.  
  101.         if(inicio >= l && fin <= r){
  102.             ans += S[i][p];
  103.             continue;
  104.         }
  105.         if(inicio < l){
  106.  
  107.             for(int j = l; j <= fin; j++){
  108.                 ans += (v[j] <= x);
  109.             }
  110.         }
  111.  
  112.         if(fin > r){
  113.             for(int j = inicio; j <= r; j++){
  114.                 ans += (v[j] <= x);
  115.             }
  116.         }
  117.     }
  118.     return ans;
  119.  
  120. }
  121. int main()
  122. {
  123.     int q; scanf("%d %d", &n, &q);
  124.  
  125.     for(int i = 0; i < n; i++){
  126.         scanf("%d", &v[i]);
  127.     }
  128.  
  129.     build();
  130.  
  131.     for(int i = 0 ; i < q; i++){
  132.         char command; scanf(" %c", &command);
  133.  
  134.         if(command == 'Q'){
  135.             int l, r, x; scanf("%d %d %d", &l, &r, &x);
  136.             l--, r--;
  137.  
  138.             printf("%d\n", query(l, r, x) );
  139.         }else{
  140.             int pos, x; scanf("%d %d", &pos, &x);
  141.             pos--;
  142.  
  143.             update(pos, x);
  144.         }
  145.     }
  146.     return 0;
  147. }
  148.  
Success #stdin #stdout 0s 3892KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ibCkwY
language:
C++ (gcc 8.3)
created:
9 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!