fork download
copy 
  1. /*
  2. http://w...content-available-to-author-only...j.com/status/KQUERY,prakhar10_10/
  3. */
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define ll long long int
  7. #define pb push_back
  8.  
  9. #define mod 1000000007
  10. #define maxn 300005
  11.  
  12. struct node{
  13.   int count;
  14.   node* left,* right;
  15.  
  16.  
  17.   node(int cnt,node* lef ,node* righ)
  18.   {count=cnt;left=lef;right=righ;}
  19.  
  20.   node* insert(int l,int r,int w);
  21.  
  22. };
  23.  
  24. node* null=new node(0,NULL,NULL);
  25.  
  26. node* node::insert(int l,int r,int w)
  27. {
  28.   if(l<=w && w<r)
  29.   {
  30.     if(l+1==r)
  31.     {return new node(this->count+1,null,null);}
  32.  
  33.     int mid=(l+r)>>1;
  34.     return new node(this->count+1,this->left->insert(l,mid,w),this->right->insert(mid,r,w));
  35.   }
  36.  
  37.   return this;
  38. }
  39.  
  40. int query(node* a,node* b,int l,int r,int k)
  41. {
  42.     if(r-1<=k)
  43.     {return 0;}
  44.     else if(k<l)
  45.     {return a->count-b->count;}
  46.  
  47.     else if(l+1==r)
  48.     {
  49.         // if(l<k)
  50.         // {return a->count-b->count;}
  51.         // else
  52.         return 0;
  53.     }
  54.  
  55.     int mid=(l+r)>>1;
  56.     int count=a->right->count-b->right->count;
  57.  
  58.     if(mid-1<=k)
  59.     {return query(a->right,b->right,mid,r,k);}
  60.  
  61.     int temp=query(a->left,b->left,l,mid,k);
  62.     return count+temp;
  63. }
  64.  
  65. #define maxq 200005
  66. int a[maxn];
  67. map<int,int>m;
  68. int l[maxq],r[maxq],k[maxq];
  69. node* root[maxn];
  70.  
  71. int main()
  72. {
  73. ios_base::sync_with_stdio(0);
  74. cin.clear();cout.clear();
  75. cin.tie(0);cout.tie(0);
  76.  
  77. int n,q,ans,l2,r2;
  78.  
  79. cin>>n;
  80. for(int i=0;i<n;++i)
  81. {cin>>a[i];
  82. m[a[i]];}
  83.  
  84. cin>>q;
  85. for(int z=0;z<q;++z)
  86. {
  87.  
  88.     cin>>l2>>r2>>k[z];
  89.     l[z]=l2-1;
  90.     r[z]=r2-1;
  91.     m[k[z]];
  92. }
  93.  
  94.  
  95. int maxi=0;
  96.   	for(map<int,int>::iterator it = m.begin(); it != m.end(); ++it)
  97.   	{
  98.     		m[it->first] = maxi;
  99.     		++maxi;
  100.   	}
  101. //all a[i]'s are mapped to 0,..,maxi-1
  102.  
  103. null->left = null->right = null;//infinte loop
  104.  
  105. root[0]=null->insert(0,maxi,m[a[0]]);
  106. for(int i=1;i<n;++i)
  107. {
  108.     root[i]=root[i-1]->insert(0,maxi,m[a[i]]);
  109. }
  110.  
  111. // cout<<maxi<<'\n';
  112.  
  113. for(int z=0;z<q;++z)
  114. {
  115.     l2=l[z];
  116.     ans=query(root[r[z]],(l2==0?null:root[l2-1]),0,maxi,m[k[z]]);
  117.     cout<<ans<<'\n';
  118. }
  119.  
  120. }
  121.  
Success #stdin #stdout 0s 21928KB
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/XQzVzV
problem KQUERY, based on SPOJ submission 19691005 (CPP14), 2017-06-27 16:11:03
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!