fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node {
  5.     Node *lpt, *rpt;
  6.     vector<int> B;
  7.  
  8.     Node() : lpt(nullptr), rpt(nullptr) {}
  9.  
  10.     Node (int* from, int* to, int low, int high) {
  11.         if (low == high || from >= to) return;
  12.         int mid = (low + high) / 2;
  13.         function<bool(int)> f = [mid] (int x) {
  14.             return x <= mid;
  15.         };
  16.  
  17.         B.reserve(to - from + 1);
  18.         B.push_back(0);
  19.         for (auto it = from; it != to; it++)
  20.             B.push_back(B.back() + f(*it));
  21.  
  22.         auto pivot = stable_partition(from, to, f);
  23.  
  24.         if (from < pivot) lpt = new Node(from, pivot, low, mid);
  25.         if (pivot < to) rpt = new Node(pivot, to, mid + 1, high);
  26.     }
  27.  
  28.     int kthSmallest (int l, int r, int k, int low, int high) {
  29.         if (l > r) return 0;
  30.         if (low == high) return low;
  31.         int cntLeft = B[r] - B[l - 1], mid = (low + high) / 2;
  32.         if (k <= cntLeft)
  33.             return lpt->kthSmallest(B[l - 1] + 1, B[r], k, low, mid);
  34.         return rpt->kthSmallest(l - B[l - 1], r - B[r], k - cntLeft, mid + 1, high);
  35.     }
  36.  
  37.     int countEqualK (int l, int r, int K, int low, int high) {
  38.         if (l > r || K < low || K > high) return 0;
  39.         if (low == high) return r - l + 1;
  40.         int mid = (low + high) / 2;
  41.         if (K <= mid) return (lpt ? lpt->countEqualK(B[l - 1] + 1, B[r], K, low, mid) : 0);
  42.         return (rpt ? rpt->countEqualK(l - B[l - 1], r - B[r], K, mid + 1, high) : 0);
  43.     }
  44.  
  45.     int countLEQ (int l, int r, int K, int low, int high) {
  46.         if (l > r || K < low) return 0;
  47.         if (high <= K) return r - l + 1;
  48.         int cntLeft = B[r] - B[l - 1], mid = (low + high) / 2;
  49.         if (K <= mid) return (lpt ? lpt->countLEQ(B[l - 1] + 1, B[r], K, low, mid) : 0);
  50.         return cntLeft + (rpt ? rpt->countLEQ(l - B[l - 1], r - B[r], K, mid + 1, high) : 0);
  51.     }
  52. };
  53.  
  54. template <int MIN, int MAX>
  55. struct WaveletTree {
  56.     Node* root;
  57.  
  58.     WaveletTree() : root(nullptr) {}
  59.     WaveletTree (int* from, int* to) : root(new Node(from, to, MIN, MAX)) {}
  60.  
  61.     int kthSmallest (int l, int r, int k) {
  62.         return root->kthSmallest(l, r, k, MIN, MAX);
  63.     }
  64.  
  65.     int countEqualK (int l, int r, int K) {
  66.         return root->countEqualK(l, r, K, MIN, MAX);
  67.     }
  68.  
  69.     int countLEQ (int l, int r, int K) {
  70.         return root->countLEQ(l, r, K, MIN, MAX);
  71.     }
  72. };
  73.  
  74. int main() {
  75. 	return 0;
  76. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/cWDg2F
language:
C++ (gcc 8.3)
created:
20 days 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!