fork download 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <algorithm>
  6. #include <set>
  7. #include <vector>
  8. #include <map>
  9. #include <queue>
  10. #include <stack>
  11.  
  12. using namespace std;
  13.  
  14. #define forn(i, n) for(int i = 0; i < int(n); i++)
  15. #define forv(i, v) for(int i = 0; i < int(v.size()); i++)
  16.  
  17. #define mp make_pair
  18. #define pb push_back
  19. #define all(x) x.begin(), x.end()
  20.  
  21.  
  22. typedef long long ll;
  23. typedef long double ld;
  24.  
  25. inline int ni() { int a; scanf("%d", &a); return a; }
  26.  
  27. const int max_n = 100000;
  28.  
  29. vector < int > values[4 * max_n];
  30. int arr[max_n];
  31. char buffer[8];
  32.  
  33. void build(int v, int l, int r) {
  34. 	if(l == r) {
  35. 		values[v].pb(arr[l]);
  36. 		return;
  37. 	}
  38.  
  39. 	int m = (l + r) / 2;
  40.  
  41. 	build(2 * v, l, m);
  42. 	build(2 * v + 1, m + 1, r);
  43.  
  44. 	forv(i, values[2 * v]) values[v].pb(values[2 * v][i]);
  45. 	forv(i, values[2 * v + 1]) values[v].pb(values[2 * v + 1][i]);
  46. 	sort(all(values[v]));
  47. }
  48.  
  49. int calc(int v, int a, int b) {
  50. 	//vector < int > :: iterator l = lower_bound(values[v].begin(), values[v].end(), a);
  51. 	//vector < int > :: iterator r = lower_bound(values[v].begin(), values[v].end(), b + 1);
  52. 	//return (r - l);
  53. 	int res = 0;
  54. 	for(int i = 0; i < int(values[v].size()); i++) {
  55. 		if(a <= values[v][i] && values[v][i] <= b) ++res;
  56. 	}
  57. 	return res;
  58. }
  59.  
  60. int query(int v, int l, int r, int tl, int tr, int a, int b) {
  61. 	if(l == tl && r == tr) {
  62. 		return calc(v, a, b);
  63. 	}
  64.  
  65. 	int res = 0, m = (l + r) / 2;
  66.  
  67. 	if(tl <= m) res += query(2 * v, l, m, tl, min(m, tr), a, b);
  68. 	if(tr > m) res += query(2 * v + 1, m + 1, r, max(m + 1, tl), tr, a, b);
  69.  
  70. 	return res;
  71. }
  72.  
  73. int main() {
  74. 	//freopen("h8.in", "r", stdin);
  75. 	//freopen("h8.out", "w", stdout);
  76.  
  77. 	int n = ni(), m = ni();
  78.  
  79. 	forn(i, n) {
  80. 		arr[i] = ni();
  81. 	}
  82.  
  83. 	build(1, 0, n - 1);
  84.  
  85. 	forn(i, m) {
  86. 		scanf("%s", buffer);
  87.  
  88. 		int l = ni() - 1;
  89. 		int r = ni() - 1;
  90. 		int a =  ni();
  91. 		int b = ni();
  92. 		printf("%d\n", query(1, 0, n - 1, l, r, a, b));
  93. 	}
  94.  
  95.  
  96.  
  97. 	return 0;
  98. }
Success #stdin #stdout 0.01s 7940KB
comments (?)
stdin 
5 1
3 4 1 3 5
GET 3 5 1 2
stdout 
0
https://ideone.com/mj3im
language:
C++ (gcc 8.3)
created:
12 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!