fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define mod 1000000007
  3. #define ll int
  4. #define big 100000000000000000
  5. using namespace std;
  6.  
  7. struct node{
  8. 	ll sz,*arr;
  9. }st[800010];
  10. ll n,q,a[30000];
  11.  
  12. void merge(ll a[],ll b[],ll c[],ll sz1,ll sz2,ll sz3){
  13. 	ll i=0,j=0,k=0;
  14. 	while(i<sz2 && j<sz3){
  15. 		if(b[i] < c[j])
  16. 			a[k++] = b[i++];
  17. 		else
  18. 			a[k++] = c[j++];
  19. 	}
  20. 	while(i < sz2)
  21. 		a[k++] = b[i++];
  22. 	while(j < sz3)
  23. 		a[k++] =  c[j++];
  24. }
  25. ll query(ll in,ll i,ll j,ll l,ll r,ll k){
  26. 	if(i>j || i>r || j<l)
  27. 		return 0;
  28. 	if(i>=l && j<=r){
  29. 		ll *temp = upper_bound(st[in].arr,st[in].arr+st[in].sz,k);
  30. 		return st[in].arr+st[in].sz-temp;
  31. 	}
  32. 	ll mid = (i+j)/2;
  33. 	ll temp1 = query(2*in+1,i,mid,l,r,k);
  34. 	ll temp2 = query(2*in+2,mid+1,j,l,r,k);
  35.  
  36. 	return temp1+temp2;
  37. }
  38. void build(ll in=0,ll i=0,ll j=n-1){
  39. 	if(i>j)
  40. 		return;
  41. 	if(i == j){
  42. 		st[in].sz = 1;
  43. 		st[in].arr = new int[1];
  44. 		st[in].arr[0] = a[i];
  45. 		return;
  46. 	}
  47. 	ll mid = (i+j)/2;
  48. 	build(2*in+1,i,mid);
  49. 	build(2*in+2,mid+1,j);
  50.  
  51. 	st[in].sz = st[2*in+1].sz+st[2*in+2].sz;
  52. 	st[in].arr = new int[st[in].sz];
  53. 	merge(st[in].arr,st[2*in+1].arr,st[2*in+2].arr,st[in].sz,st[2*in+1].sz,st[2*in+2].sz);
  54. }
  55. int main(){
  56. //	freopen("input.txt","r",stdin);
  57. //	ios::sync_with_stdio(0);
  58.  
  59. 	ll l,r,i,k,j;
  60.  
  61. 	scanf("%d",&n);
  62. 	for(i=0;i<n;i++)
  63. 		scanf("%d",&a[i]);
  64. 	build();
  65. /*	for(i=0;i<2*n;i++){
  66. 		cout<<i<<"-";
  67. 		for(j=0;j<st[i].sz;j++)
  68. 			cout<<st[i].arr[j]<<" ";
  69. 		cout<<"\n";
  70. 	}*/
  71. 	scanf("%d",&q);
  72. 	while(q--){
  73. 		scanf("%d%d%d",&l,&r,&k);
  74. 		l--;r--;
  75. 		printf("%d\n",query(0,0,n-1,l,r,k));
  76. 	}
  77. 	return 0;
  78. }
  79.  
Success #stdin #stdout 0s 9784KB
comments (?)
stdin
copy 
12
5 1 2 3 4 5 2 3 1 2 12 1
6
2 4 1
4 4 4
1 5 2 
2 8 7
4 9 3
7 10 1
stdout
copy 
2
0
3
0
2
3
https://ideone.com/iNSQ1M
language:
C++ (gcc 8.3)
created:
8 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!