fork(14) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  6. #define ll long long
  7. #define si(x) scanf("%d",&x)
  8. #define sl(x) scanf("%lld",&x)
  9. #define ss(s) scanf("%s",s)
  10. #define pi(x) printf("%d\n",x)
  11. #define pl(x) printf("%lld\n",x)
  12. #define ps(s) printf("%s\n",s)
  13. #define deb(x) cout << #x << "=" << x << endl
  14. #define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
  15. #define pb push_back
  16. #define mp make_pair
  17. #define F first
  18. #define S second
  19. #define all(x) x.begin(), x.end()
  20. #define clr(x) memset(x, 0, sizeof(x))
  21. #define sortall(x) sort(all(x))
  22. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  23. #define PI 3.1415926535897932384626
  24. typedef pair<int, int> pii;
  25. typedef pair<ll, ll> pl;
  26. typedef vector<int> vi;
  27. typedef vector<ll> vl;
  28. typedef vector<pii> vpii;
  29. typedef vector<pl> vpl;
  30. typedef vector<vi> vvi;
  31. typedef vector<vl> vvl;
  32. int mpow(int base, int exp);
  33. void ipgraph(int m);
  34. void dfs(int u, int par);
  35. const int mod = 1000000007;
  36. const int N = 3e5, M = N;
  37. //=======================
  38. const int MAX = 1e6;
  39. vi g[N];
  40. int a[N];
  41. struct wavelet_tree{
  42. #define vi vector<int>
  43. #define pb push_back
  44. int lo, hi;
  45. wavelet_tree *l, *r;
  46. vi b;
  47.  
  48. //nos are in range [x,y]
  49. //array indices are [from, to)
  50. wavelet_tree(int *from, int *to, int x, int y){
  51. lo = x, hi = y;
  52. if(lo == hi or from >= to) return;
  53. int mid = (lo+hi)/2;
  54. auto f = [mid](int x){
  55. return x <= mid;
  56. };
  57. b.reserve(to-from+1);
  58. b.pb(0);
  59. for(auto it = from; it != to; it++)
  60. b.pb(b.back() + f(*it));
  61. //see how lambda function is used here
  62. auto pivot = stable_partition(from, to, f);
  63. l = new wavelet_tree(from, pivot, lo, mid);
  64. r = new wavelet_tree(pivot, to, mid+1, hi);
  65. }
  66.  
  67. //kth smallest element in [l, r]
  68. int kth(int l, int r, int k){
  69. if(l > r) return 0;
  70. if(lo == hi) return lo;
  71. int inLeft = b[r] - b[l-1];
  72. int lb = b[l-1]; //amt of nos in first (l-1) nos that go in left
  73. int rb = b[r]; //amt of nos in first (r) nos that go in left
  74. if(k <= inLeft) return this->l->kth(lb+1, rb , k);
  75. return this->r->kth(l-lb, r-rb, k-inLeft);
  76. }
  77.  
  78. //count of nos in [l, r] Less than or equal to k
  79. int LTE(int l, int r, int k) {
  80. if(l > r or k < lo) return 0;
  81. if(hi <= k) return r - l + 1;
  82. int lb = b[l-1], rb = b[r];
  83. return this->l->LTE(lb+1, rb, k) + this->r->LTE(l-lb, r-rb, k);
  84. }
  85.  
  86. //count of nos in [l, r] equal to k
  87. int count(int l, int r, int k) {
  88. if(l > r or k < lo or k > hi) return 0;
  89. if(lo == hi) return r - l + 1;
  90. int lb = b[l-1], rb = b[r], mid = (lo+hi)/2;
  91. if(k <= mid) return this->l->count(lb+1, rb, k);
  92. return this->r->count(l-lb, r-rb, k);
  93. }
  94. ~wavelet_tree(){
  95. delete l;
  96. delete r;
  97. }
  98. };
  99. int main()
  100. {
  101. ios_base::sync_with_stdio(false);
  102. cin.tie(NULL);
  103. srand(time(NULL));
  104. int i,n,k,j,q,l,r;
  105. cin >> n;
  106. fo(i, n) cin >> a[i+1];
  107. wavelet_tree T(a+1, a+n+1, 1, MAX);
  108. cin >> q;
  109. while(q--){
  110. int x;
  111. cin >> x;
  112. cin >> l >> r >> k;
  113. if(x == 0){
  114. //kth smallest
  115. cout << "Kth smallest: ";
  116. cout << T.kth(l, r, k) << endl;
  117. }
  118. if(x == 1){
  119. //less than or equal to K
  120. cout << "LTE: ";
  121. cout << T.LTE(l, r, k) << endl;
  122. }
  123. if(x == 2){
  124. //count occurence of K in [l, r]
  125. cout << "Occurence of K: ";
  126. cout << T.count(l, r, k) << endl;
  127. }
  128. }
  129. return 0;
  130. }
  131.  
  132.  
Success #stdin #stdout 0s 23448KB
stdin
7
1 2 3 3 5 4 2
4
0 5 7 1
0 5 7 2
1 2 6 4
2 2 5 3 
stdout
Kth smallest: 2
Kth smallest: 4
LTE: 4
Occurence of K: 2