fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define fast ios_base::sync_with_stdio(false);cin.tie(0);
  3. #define gc getchar_unlocked
  4. using namespace std;
  5. typedef long long  lli;
  6.  
  7. void scanint(lli &x)
  8. {
  9.     register lli c = gc();
  10.     x = 0;
  11.     for(;(c<48 || c>57);c = gc());
  12.     for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  13. }
  14.  
  15. void build_tree(lli a[], vector<lli>st[], lli low, lli high, lli pos){
  16.     if(low==high){
  17.         st[pos].push_back(a[low]);
  18.         return;
  19.     }
  20.     else{
  21.         lli mid = (low+high)/2;
  22.         build_tree(a,st,low,mid,2*pos);
  23.         build_tree(a,st,mid+1,high,2*pos+1);
  24.         merge(st[2*pos].begin(),st[2*pos].end(),st[2*pos+1].begin(),st[2*pos+1].end(),back_inserter(st[pos]));
  25.     }
  26. }
  27.  
  28. lli RMQ(vector<lli> st[], lli qlow, lli qhigh, lli k , lli low ,lli high, lli pos){
  29.     if(qlow>high || qhigh<low)
  30.         return 0;
  31.     if(qlow<=low && qhigh>=high){
  32.         return st[pos].size() - (upper_bound(st[pos].begin(),st[pos].end(),k)-st[pos].begin());
  33.     }
  34.         lli mid = (low+high)/2;
  35.         return RMQ(st,qlow,qhigh,k,low,mid,2*pos) + RMQ(st,qlow,qhigh,k,mid+1,high,2*pos+1);
  36.  
  37. }
  38.  
  39.  
  40. void dispalyTree(vector<lli>st[], lli n){
  41.         cout<<"\nDisplaying tree\n;";
  42.         for(int i=1;i<=4*n;i+=1){
  43.             cout<<"\ni="<<i<<"\n";
  44.             for(auto it=st[i].begin();it!=st[i].end();it++)
  45.                 cout<<*it<<" ";
  46.         }
  47.         cout<<"\nends here\n";
  48. }
  49.  
  50. int main(){
  51.     //fast;
  52.     lli n;
  53.     scanint(n);
  54.     lli a[n+1];
  55.     for(int i=1;i<=n;i++){
  56.         scanint(a[i]);
  57.     }
  58.     vector<lli> st[4*n+1];
  59.     build_tree(a,st,1,n,1);
  60.     //dispalyTree(st,n);
  61.     lli q,i,j,k;
  62.     int ans=0;
  63.     //cin>>q;
  64.     scanint(q);
  65.     while(q--){
  66.         //cin>>i>>j>>k;
  67.         scanint(i);
  68.         scanint(j);
  69.         scanint(k);
  70.         if(i<1)
  71.             i=1;
  72.         if(j>n)
  73.             j=n;
  74.         ans = RMQ(st,i,j,k,1,n,1);
  75.         //cout<<ans<<"\n";
  76.          printf("%lld\n",ans);
  77.     }
  78. }
  79.  
  80.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
stdout
copy 
2
0
3
https://ideone.com/gzjsB3
language:
C++ (gcc 8.3)
created:
6 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!