fork download
copy 
  1. #include <cstdio>
  2. #include <iterator>
  3. #include <utility>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <set>
  7. #include <tuple>
  8. #include <iostream>
  9. using namespace std;
  10.  
  11. typedef pair<int,int> pii;
  12. typedef vector<int> vi;
  13. typedef vector<pii> vii;
  14. typedef long long ll;
  15.  
  16. #define FOR(i,S,E) for(int i=S; i<E; i++)
  17. #define ri(x) scanf("%d", &x)
  18. #define rii(x,y) scanf("%d%d", &x, &y)
  19. #define fst first
  20. #define snd second
  21. #define mp make_pair
  22. #define mt make_tuple
  23. #define pb push_back
  24.  
  25. const int INF = 1e9, MAXN = 3e4 + 10;
  26.  
  27. int n, q;
  28. vector<pii> v;
  29.  
  30. // BIT (tambien se llaman fenwick tree)
  31.  
  32.  
  33. //	Empieza con puros 0, suponiendo que tienen un arreglo A[] inicial, tienen
  34. //que meterlo en el BIT a lo brutico, iterando sobre A y haciendo puros updates
  35.  
  36. ll BIT[MAXN];
  37.  
  38. //suma val a la posicion p, tengan en cuenta que esto no modifica A, a veces se quiere
  39. //modificar, entonces lo tienen que hacer tambien a parte.
  40. void BIT_upd(int p, int val){ //O(log(n))
  41. 	p++;
  42. 	for(; p <= n; p += p & -p)
  43. 		BIT[p] += val;
  44. }
  45.  
  46. //devuelve la suma de [1,p]
  47. int BIT_sum(int p){ //O(log(n))
  48. 	int ret = 0;
  49. 	p++;
  50. 	for(; p; p -= p & -p)
  51. 		ret += BIT[p];
  52. 	return ret;
  53. }
  54.  
  55. struct t {
  56.     int s, k, id;
  57. };
  58.  
  59. bool comp1 (t &a, t &b) {
  60.     return a.s < b.s;
  61. }
  62.  
  63. int main () {
  64.     ri(n);
  65.     vector< t > sL, sR;
  66.     FOR(i,0,n) {
  67. 		int inp; ri(inp);
  68. 		v.pb(mp(inp,0));
  69.     }
  70.     ri(q);
  71.     vi Q;
  72.     Q.resize(q, 0);
  73.     FOR(i,0,q) {
  74. 		int l,r,k;
  75. 		rii(l,r); ri(k);
  76. 		sL.pb({l-2, k, i});
  77. 		sR.pb({--r,k, i});
  78.     }
  79.     sort(sL.begin(), sL.end(), comp1);
  80.     sort(sR.begin(), sR.end(), comp1);
  81.  
  82.     vi aux;
  83.     FOR(i,0,n) aux.pb(v[i].fst);
  84.     sort(aux.begin(), aux.end());
  85.     aux.resize(distance(aux.begin(), unique(aux.begin(), aux.end())));
  86.     FOR(i,0,n) v[i].snd = distance(aux.begin(), lower_bound(aux.begin(), aux.end(), v[i].fst));
  87.     vii aux2 = v;
  88.     sort(aux2.begin(), aux2.end());
  89. 	aux2.resize(distance(aux2.begin(), unique(aux2.begin(), aux2.end())));
  90. 	/*
  91. 	FOR(i,0,aux.size()) {
  92. 		printf("(%d, %d) ", aux2[i].fst, aux2[i].snd);
  93. 	}
  94. 	printf("\n");
  95. 	*/
  96.  
  97.     int id=0, jd=0;
  98.     FOR(i,0,n) {
  99. 		BIT_upd(v[i].snd, 1);
  100. 		//printf("UPD: %d\n", v[i].snd);
  101. 		while( id < q and sL[id].s == -1) id++;
  102. 		while (id < q and i == sL[id].s) {
  103. 			int k = sL[id].k;
  104. 			auto it = lower_bound(aux2.begin(), aux2.end(), mp(k,-INF));
  105. 			int x; //cantidad de elementos mayores a k
  106. 			if ((*it).fst != k and it != aux2.begin()) {
  107. 				it--;
  108. 				x = BIT_sum((*it).snd);
  109. 			}
  110. 			else if ((*it).fst != k and it == aux2.begin())
  111. 				x = 0;
  112. 			else {
  113. 				x = BIT_sum((*it).snd);
  114. 				//printf("\tK: (%d, %d)\n", (*it).fst, (*it).snd);
  115. 			}
  116.  
  117. 			//printf("\t%d -= %d - %d\n", Q[(sL[id].id)], BIT_sum(n-1), BIT_sum(x));
  118. 			Q[(sL[id].id)] -= BIT_sum(n-1) - x;
  119. 			id++;
  120. 		}
  121. 		while(jd < q and i == sR[jd].s) {
  122. 			int k = sR[jd].k;
  123. 			auto it = lower_bound(aux2.begin(), aux2.end(), mp(k, -INF));
  124.  
  125. 			int x; //cantidad de elementos mayores a k
  126. 			if ((*it).fst != k and it != aux2.begin()) {
  127. 				it--;
  128. 				x = BIT_sum((*it).snd);
  129. 			}
  130. 			else if ((*it).fst != k and it == aux2.begin())
  131. 				x = 0;
  132. 			else
  133. 				x = BIT_sum((*it).snd);
  134. 			Q[sR[jd].id] += BIT_sum(n-1) - x;
  135.  
  136. 			jd++;
  137. 		}
  138.     }
  139.  
  140.     FOR(i,0,q) {
  141. 		printf("%d\n", Q[i]);
  142.     }
  143.  
  144. }
  145.  
Success #stdin #stdout 0s 3716KB
comments (?)
stdin
copy 
10
25 12 31 2 15 35 15 36 100 1000
10
1 10 15
2 9 2
3 8 16
4 7 25
5 6 10
6 6 3
6 6 100
2 6 34
1 6 3
3 7 14
stdout
copy 
6
7
3
1
2
1
0
1
5
4
https://ideone.com/22FvI4
problem KQUERY, based on SPOJ submission 18563364 (C++14), 2017-01-12 15:11:37
language:
C++14 (gcc 8.3)
created:
7 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!