fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. using namespace __gnu_pbds;
  5. #define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
  6. #define ll int
  7. #define ld long double
  8. //#define int long long
  9. #define endl "\n"
  10. #define yes cout<<"YES"<<endl;
  11. #define no cout<<"NO"<<endl;
  12. #define pb push_back
  13. //#pragma GCC optimize("O3,unroll-loops")
  14. //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  15. using namespace std;
  16. const int MOD = 1e9 + 7;
  17. //const int MOD = 998244353  ;
  18. const int N_Max = 2e5 + 5;
  19. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
  20.  
  21. struct Query {
  22.     int id, l, r, mx, mn;
  23. };
  24.  
  25. Query qry[N_Max];
  26. int ans[N_Max];
  27. int a[N_Max];
  28. int N, Q;
  29. int l, r;
  30. int res[N_Max + 1];
  31. const int Bl = 448;
  32. int bloc[Bl + 5];
  33.  
  34.  
  35. void add(int val) {
  36.     res[a[val]]++;
  37.     bloc[a[val] / Bl]++;
  38. }
  39.  
  40. void rmv(int val) {
  41.     res[a[val]]--;
  42.     bloc[a[val] / Bl]--;
  43. }
  44.  
  45. void update(int id) {
  46.     while (r < qry[id].r) add(++r);
  47.  
  48.     while (l > qry[id].l) add(--l);
  49.  
  50.     while (r > qry[id].r) rmv(r--);
  51.  
  52.     while (l < qry[id].l) rmv(l++);
  53. }
  54.  
  55. int query(int mn, int mx) {
  56.     if(mn>mx){
  57.         return 0;
  58.     }
  59.     ll aux = 0;
  60.     ll bloc1 = mn / Bl;
  61.     ll bloc2 = mx / Bl;
  62.     if (bloc1 == bloc2) {
  63.         for (int i = mn; i <= mx; i++) {
  64.             aux += res[i];
  65.         }
  66.     } else {
  67.         for (int i = mn; i < (bloc1 + 1) * Bl; i++) {
  68.             aux += res[i];
  69.         }
  70.         for (int i = bloc1 + 1; i < bloc2; i++) {
  71.             aux += bloc[i];
  72.         }
  73.         for (int i = bloc2 * Bl; i <= mx; i++) {
  74.             aux += res[i];
  75.         }
  76.     }
  77.     return aux;
  78. }
  79.  
  80. void mo() {
  81.     int B = sqrt(2 * N);
  82.     sort(qry + 1, qry + Q + 1, [B](Query a, Query b) { return make_pair(a.l / B, a.r) < make_pair(b.l / B, b.r); });
  83.     l = 1, r = 0;
  84.     for (int i = 1; i <= Q; i++) {
  85.         update(i);
  86.         ans[qry[i].id] = query(qry[i].mn, qry[i].mx);
  87.     }
  88. }
  89.  
  90.  
  91. void solve() {
  92.     cin>>N>>Q;
  93.     vector<ll> comp;
  94.     for(int i=1;i<=N;i++){
  95.         cin>>a[i];
  96.         comp.pb(a[i]);
  97.     }
  98.     sort(comp.begin(), comp.end());
  99.     comp.erase(unique(comp.begin(), comp.end()),comp.end());
  100.     for(int i=1;i<=N;i++){
  101.         a[i]= lower_bound(comp.begin(), comp.end(),a[i])-comp.begin();
  102.     }
  103.     for(int i=1;i<=Q;i++){
  104.         cin>>qry[i].l>>qry[i].r>>qry[i].mn>>qry[i].mx;
  105.         qry[i].mn= lower_bound(comp.begin(), comp.end(),qry[i].mn)-comp.begin();
  106.         qry[i].mx= upper_bound(comp.begin(), comp.end(),qry[i].mx)-comp.begin()-1;
  107.         qry[i].id=i;
  108.     }
  109.     mo();
  110.     for(int i=1;i<=Q;i++){
  111.         cout<<ans[i]<<endl;
  112.     }
  113. }
  114.  
  115. signed main() {
  116.     FAST;
  117.     auto begin = std::chrono::high_resolution_clock::now();
  118. #ifndef ONLINE_JUDGE
  119.     freopen("input.txt", "r", stdin);
  120.     freopen("output.txt", "w", stdout);
  121. #endif
  122.     ll t = 1;
  123.     //cin>>t;
  124.     while (t--) solve();
  125. #ifndef ONLINE_JUDGE
  126.     auto end = std::chrono::high_resolution_clock::now();
  127.     cout << setprecision(4) << fixed;
  128.     cout << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count()
  129.          << " seconds" << endl;
  130. #endif
  131. }
  132.  
  133.  
  134.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yd6fAi
language:
C++14 (clang 8.0)
created:
2 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!