fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e5;
  5.  
  6. struct wavelet {
  7. 	int lo, hi;
  8. 	wavelet *l, *r;
  9. 	vector<int> b;
  10.  
  11. 	wavelet(int *from, int *to, int x, int y) {
  12. 		lo = x, hi = y;
  13. 		if(lo == hi || from >= to)
  14. 			return;
  15. 		int m = (lo + hi) >> 1;
  16. 		auto f = [m](int x) {
  17. 			return x <= m;
  18. 		};
  19. 		b.reserve(to - from + 1);
  20. 		b.push_back(0);
  21. 		for(auto i = from; i != to; i++)
  22. 			b.push_back(b.back() + f(*i));
  23. 		auto pivot = stable_partition(from, to, f);
  24. 		l = new wavelet(from, pivot, lo, m);
  25. 		r = new wavelet(pivot, to, m + 1, hi);
  26. 	}
  27.  
  28. 	int kth(int l, int r, int k) {
  29. 		if(l > r) return 0;
  30. 		if(lo == hi) return lo;
  31. 		int in_left = b[r] - b[l - 1];
  32. 		int lb = b[l - 1];
  33. 		int rb = b[r];
  34. 		if(k <= in_left)
  35. 			return this->l->kth(lb + 1, rb, k);
  36. 		return this->r->kth(l - lb, r - rb, k - in_left);
  37. 	}
  38.  
  39. 	~wavelet() {
  40. 		delete l;
  41. 		delete r;
  42. 	}
  43. };
  44.  
  45. int a[N];
  46.  
  47. int main() {
  48. 	int n, q;
  49. 	scanf("%d %d", &n, &q);
  50. 	for(int i = 1; i <= n; ++i) {
  51. 		scanf("%lld", a + i);
  52. 	}
  53. 	wavelet w(a + 1, a + n + 1, 1, n + 1);
  54. 	while(q--) {
  55. 		int l, r, k;
  56. 		scanf("%d %d %d", &l, &r, &k);
  57. 		printf("%d\n", w.kth(l, r, k));
  58. 	}
  59. }
Success #stdin #stdout 0s 16024KB
comments (?)
stdin
copy 
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
stdout
copy 
5
6
3
https://ideone.com/G6uAWY
language:
C++14 (clang 8.0)
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!