verify/library_checker-range_kth_smallest.cpp

View this file on GitHub
Last update: 2026-06-05 22:09:56+09:00
Problem: https://judge.yosupo.jp/problem/range_kth_smallest

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/range_kth_smallest"

#include <bits/stdc++.h>
using namespace std;

#include "templates/alias.hpp"
#include "templates/macro.hpp"

#include "data-structure/wavelet_matrix.hpp"

int main() {
  ll N, Q;
  in(N, Q);

  vi A(N);
  in(A);

  WaveletMatrix<ll, 30> wm(A);

  while (Q--) {
    ll l, r, k;
    in(l, r, k);

    cout << wm.kth_smallest(l, r, k) << "\n";
  }
}

#line 1 "verify/library_checker-range_kth_smallest.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_kth_smallest"

#include <bits/stdc++.h>
using namespace std;

#line 7 "templates/alias.hpp"

template <class T> using VC = std::vector<T>;
template <class T>
using rpriority_queue = std::priority_queue<T, VC<T>, std::greater<T>>;
using ll = long long;
using ld = long double;
using pii = std::pair<ll, ll>;
using vi = VC<ll>;
using vvi = VC<vi>;
using vvvi = VC<vvi>;
using vb = VC<bool>;
using vvb = VC<vb>;
using vf = VC<double>;
using vvf = VC<vf>;
using vpii = VC<pii>;
using vvpii = VC<vpii>;
using si = std::set<ll>;
using spii = std::set<pii>;
using mii = std::map<ll, ll>;
const std::string upperlist = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const std::string lowerlist = "abcdefghijklmnopqrstuvwxyz";
#define mp make_pair
#define dms << " " <<

constexpr int MOD998 = 998244353;
#line 4 "templates/macro.hpp"

// 引数の長さで内容が変わるrep 参考: https://trap.jp/post/1224
#define overload4(a, b, c, d, ...) d
#define _rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(...) overload4(__VA_ARGS__, REP, _rep)(__VA_ARGS__)
#define _rrep(i, n) for (int i = n - 1; i >= 0; i--)
#define RREP(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); i--)
#define rrep(...) overload4(__VA_ARGS__, RREP, _rrep)(__VA_ARGS__)

#define all(a) (a).begin(), (a).end()

template <typename T> bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T> bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
  for (T &in : v)
    is >> in;
  return is;
}

template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    os << v[i] << (i + 1 == v.size() ? "" : " ");
  }
  return os;
}

// pythonのprintライクな関数 参考:
// https://nyaannyaan.github.io/library/template/inout.hpp
inline void out() { std::cout << std::endl; }
template <typename T, typename... U, char sep = ' '>
void out(const T &t, const U &...u) {
  std::cout << t;

  if (sizeof...(u))
    std::cout << sep;

  out(u...);
}

// cinの短縮関数 参考: https://nyaannyaan.github.io/library/template/inout.hpp
inline void in() {}
template <typename T, class... U> void in(T &t, U &...u) {
  std::cin >> t;
  in(u...);
}

template <typename T> inline T ceil_div(T a, T b) { return (a + b - 1) / b; }
template <typename T> inline T mod_pow(T a, T n, T mod) {
  T res = 1;
  while (n) {
    if (n % 2 != 0) {
      res *= a;
      res %= mod;
    }

    a *= a;
    a %= mod;

    n >>= 1;
  }

  return res;
}
template <typename T> inline T minus_mod(T a, T b) { return ((a % b) + b) % b; }

template <typename T> void apply_vec(std::vector<T> &v, T (*fn)(T)) {
  for (int i = 0; i < v.size(); i++)
    v[i] = fn(v[i]);
}
#line 8 "verify/library_checker-range_kth_smallest.cpp"

#line 3 "data-structure/wavelet_matrix.hpp"

struct BitVector {
  using u64 = uint64_t;

  int n;
  std::vector<u64> bit;
  std::vector<u64> cnt;

  BitVector() {};
  BitVector(int N) {
    n = (N + 63) / (64);
    bit.resize(n + 1, 0), cnt.resize(n + 1, 0);
  }
  void set(int i) { bit[i / 64] |= 1LL << (i & 63); }
  void build() {
    for (int i = 0; i < n; i++)
      cnt[i + 1] += cnt[i] + std::popcount(bit[i]);
  }
  int rank(int i) {
    return cnt[i / 64] + std::popcount(bit[i / 64] & ((1ull << (i & 63)) - 1));
  }
};

template <std::integral Tp, int H = 64> struct WaveletMatrix {
  int N;
  std::array<BitVector, H> dir;

  WaveletMatrix(std::vector<Tp> A) : N{A.size()} {
    for (int b = H - 1; b >= 0; --b) {
      BitVector bv(N);

      std::vector<Tp> left, right;

      for (int i = 0; i < N; i++) {
        if ((A[i] >> b) & 1) {
          right.emplace_back(A[i]);
          bv.set(i);
        } else
          left.emplace_back(A[i]);
      }

      for (int i = 0; i < left.size(); i++)
        A[i] = left[i];
      for (int i = 0; i < right.size(); i++)
        A[i + left.size()] = right[i];

      bv.build();
      dir[b] = bv;
    }
  }

  //! [left,right)の区間で、xより大きい値の個数を求める
  int upper_cnt(int left, int right, Tp x) {
    int res = 0;

    for (int b = H - 1; b >= 0; b--) {
      int lc = dir[b].rank(left), rc = dir[b].rank(right), nl, nr;

      if ((x >> b) & 1) {
        if (lc == rc)
          break;

        nl = N - dir[b].rank(N) + lc, nr = nl + rc - lc;
      } else {
        res += rc - lc;

        if ((right - left) == (rc - lc))
          break;

        nl = left - lc, nr = right - rc;
      }

      std::swap(left, nl), std::swap(right, nr);
    }

    return res;
  }

  //! [left,right)の区間で、x未満の値の個数を求める
  int lower_cnt(int left, int right, Tp x) {
    int res = 0;

    for (int b = H - 1; b >= 0; b--) {
      int lc = dir[b].rank(left), rc = dir[b].rank(right), nl, nr;

      if ((x >> b) & 1) {
        res += (right - left) - (rc - lc);

        if (lc == rc)
          break;

        nl = N - dir[b].rank(N) + lc, nr = nl + rc - lc;
      } else {
        if ((right - left) == (rc - lc))
          break;

        nl = left - lc, nr = right - rc;
      }

      std::swap(left, nl), std::swap(right, nr);
    }

    return res;
  }

  //! [left,right)のなかでk番目(0-indexed)に大きい値を求める
  Tp kth_largest(int left, int right, int k) {
    Tp res = 0;

    for (int b = H - 1; b >= 0; b--) {
      int lc = dir[b].rank(left), rc = dir[b].rank(right), nl, nr;

      if (rc - lc > k) {
        res += Tp(1) << b;
        nl = N - dir[b].rank(N) + lc, nr = nl + rc - lc;
      } else {
        k -= rc - lc;
        nl = left - lc, nr = right - rc;
      }

      std::swap(left, nl), std::swap(right, nr);
    }

    return res;
  }

  //! [left,right)のなかでk番目(0-indexed)に小さい値を求める
  Tp kth_smallest(int left, int right, int k) {
    return kth_largest(left, right, (right - left) - k - 1);
  }
};
#line 10 "verify/library_checker-range_kth_smallest.cpp"

int main() {
  ll N, Q;
  in(N, Q);

  vi A(N);
  in(A);

  WaveletMatrix<ll, 30> wm(A);

  while (Q--) {
    ll l, r, k;
    in(l, r, k);

    cout << wm.kth_smallest(l, r, k) << "\n";
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_zero_00	AC	10 ms	4 MB
g++	dense_large_a_00	AC	533 ms	4 MB
g++	dense_small_a_00	AC	296 ms	3 MB
g++	example_00	AC	2 ms	3 MB
g++	max_random_00	AC	629 ms	11 MB
g++	max_random_01	AC	614 ms	11 MB
g++	max_random_02	AC	627 ms	11 MB
g++	max_random_03	AC	655 ms	11 MB
g++	max_random_04	AC	666 ms	11 MB
g++	random_00	AC	428 ms	8 MB
g++	random_01	AC	650 ms	9 MB
g++	random_02	AC	310 ms	5 MB
g++	random_03	AC	207 ms	10 MB
g++	random_04	AC	354 ms	4 MB
g++	small_00	AC	3 ms	3 MB
g++	small_01	AC	3 ms	3 MB
g++	small_02	AC	3 ms	3 MB
g++	small_03	AC	4 ms	3 MB
g++	small_04	AC	6 ms	3 MB
g++	small_05	AC	4 ms	3 MB
g++	small_06	AC	4 ms	3 MB
g++	small_07	AC	3 ms	3 MB
g++	small_08	AC	4 ms	3 MB
g++	small_09	AC	6 ms	3 MB