Guest User

Untitled

a guest
Sep 24th, 2019
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define maxn 100010
  3. #define range(v) v.begin(),v.end()
  4. using namespace std;
  5. vector<int> st[4*maxn],a(maxn,0);
  6.  
  7. void build(int s,int e,int index)
  8. {
  9.     if(s==e)
  10.     {
  11.         st[index].push_back(a[s]);
  12.         return;
  13.     }
  14.     int mid = (s+e)/2;
  15.     int l=2*index+1;
  16.     int r=2*index+2;
  17.     build(s,mid,l);
  18.     build(1+mid,e,r);
  19.     merge(range(st[l]),range(st[r]),back_inserter(st[index]));
  20.     return;
  21. }
  22.  
  23. int query(int index,int s,int e,int qs,int qe,int k)
  24. {
  25.     if(s>qe || e<qs)
  26.     {
  27.         return 0;
  28.     }
  29.     if(qs<=s && qe<=e)
  30.     {
  31.         return e-s+1-(lower_bound(st[index].begin(),st[index].end(),k)-st[index].begin());
  32.     }
  33.     int mid=(s+e)/2;
  34.     return query(2*index+1,s,mid,qs,qe,k)+query(2*index+2,1+mid,e,qs,qe,k);
  35. }
  36. int main()
  37. {
  38.     ios_base::sync_with_stdio(false);
  39.     int n;
  40.     cin>>n;
  41.     for(int i=0;i<n;i++)
  42.     {
  43.         cin>>a[i];
  44.     }
  45.     build(0,n-1,0);
  46.     int q;
  47.     cin>>q;
  48.     while(q--)
  49.     {
  50.         int l,r,k;
  51.         cin>>l>>r>>k;
  52.         int ans = query(0,0,n-1,l-1,r-1,k);
  53.             cout<<ans<<endl;
  54.     }
  55.     return 0;
  56. }
Add Comment
Please, Sign In to add comment