fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4. int n , q;
  5. cin >> n >> q;
  6.  
  7. vector<int> a(n);
  8. for(int i=0;i<n;++i)cin >> a[i];
  9.  
  10. vector<int> red = a;
  11. vector<vector<int>> queries;
  12. for(int i=0;i<q;++i){
  13. int l,r,v1,v2;
  14. cin >> l >> r >> v1 >> v2 ;
  15.  
  16. queries.push_back({r,v2,i,1});
  17. queries.push_back({l,v1-1,i,-1});
  18. red.push_back(v2);
  19. red.push_back(v1-1);
  20. }
  21.  
  22. sort(begin(red), end(red));
  23. red.erase( unique(begin(red), end(red)) , end(red));
  24. int m = red.size() + 2;
  25.  
  26. sort(begin(queries), end(queries));
  27. vector<int> bit(m,0);
  28.  
  29. auto update = [&](int index,int value)->void{
  30. for(;index<m;index+=index&-index)bit[index]+=value;
  31. };
  32.  
  33. auto ask = [&](int index)->int{
  34. int ret=0;
  35. for(;index>0;index-=index&-index) ret += bit[index];
  36. return ret;
  37. };
  38.  
  39. auto compressed_value = [&](int val)->int{
  40. return lower_bound(begin(red), end(red), val) - begin(red) + 1;
  41. };
  42.  
  43. int it = 0;
  44.  
  45. vector<int> answer(q,0);
  46. for(auto query : queries){
  47. const int value = compressed_value(query[1]);
  48. for(;it<n && it<=query[0];++it) update( compressed_value(a[it]), 1);
  49. answer[query[2]] += query[3] * ask(value);
  50. }
  51.  
  52. for(int i=0;i<q;++i) cout << answer[i] << "\n" ;
  53. }
Success #stdin #stdout 0.01s 5476KB
stdin
Standard input is empty
stdout
Standard output is empty