test/ds/pssgt2.test.cpp

• View this file on GitHub
• Last update: 2025-10-04 16:32:33+08:00
• Problem: https://judge.yosupo.jp/problem/range_kth_smallest

Depends on

• src/ds/pssgt.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_kth_smallest
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define PUSHB push_back
using namespace std;

#include "../../src/ds/pssgt.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  vector<int> a(n), dc(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    dc[i] = a[i];
  }
  sort(ALL(dc)), dc.erase(unique(ALL(dc)), dc.end());
  int N = dc.size();
  map<int, int> mp;
  for (int i = 0; i < N; i++) {
    mp[dc[i]] = i;
  }
  for (auto& x : a) {
    x = mp[x];
  }
  SegTree<Info> sgt(N);
  vector<int> buf(N);
  for (int i = 0; i < n; i++) {
    buf[a[i]]++;
    sgt.set(sgt.root.back(), a[i], Info{buf[a[i]]});
  }

  while (q--) {
    int l, r, k;
    cin >> l >> r >> k;
    int qry = sgt.bsearch(sgt.root[l], sgt.root[r],
                          [&](Info x) { return x.data <= k; });
    cout << dc[qry] << "\n";
  }
  return 0;
}

#line 1 "test/ds/pssgt2.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_kth_smallest
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define PUSHB push_back
using namespace std;

#line 1 "src/ds/pssgt.hpp"
template <typename Info>
struct SegTree {
  struct Node {
    Info info = {};
    int ls = -1, rs = -1;
  };
  int n, _pos, _l, _r;
  Info _v, _acc;
  vector<int> root;
  vector<Node> tree;
  SegTree(int n) : SegTree(vector<Info>(n)) {}
  SegTree(const vector<Info>& a) : n(a.size()) { root.PUSHB(build(0, n, a)); }
  void set(int p, int pos, Info f) {
    _pos = pos, _v = f, root.PUSHB(set_(p, 0, n));
  }
  Info sum(int p1, int p2, int l, int r) {
    return _l = l, _r = r, sum_(p1, p2, 0, n);
  }
  template <typename P>
  int bsearch(int p1, int p2, P pred) {
    return _acc = {}, bsearch_(p1, p2, 0, n, pred);
  }

 private:
#define MID (pl + (pr - pl) / 2)
  int new_(Node node) { return tree.PUSHB(move(node)), tree.size() - 1; }
  int pushup(int ls, int rs) {
    return new_(Node{tree[ls].info + tree[rs].info, ls, rs});
  }
  int build(int pl, int pr, const vector<Info>& a) {
    if (pr - pl == 1) return new_({a[pl], -1, -1});
    return pushup(build(pl, MID, a), build(MID, pr, a));
  }
  int set_(int p, int pl, int pr) {
    if (_pos < pl || pr <= _pos) return p;
    if (pr - pl == 1) return new_(Node{_v, -1, -1});
    return pushup(set_(tree[p].ls, pl, MID), set_(tree[p].rs, MID, pr));
  }
  Info sum_(int p1, int p2, int pl, int pr) {
    if (_r <= pl || pr <= _l) return {};
    if (_l <= pl && pr <= _r) return tree[p2].info - tree[p1].info;
    return sum_(tree[p1].ls, tree[p2].ls, pl, MID) +
           sum_(tree[p1].rs, tree[p2].rs, MID, pr);
  }
  template <typename P>
  int bsearch_(int p1, int p2, int pl, int pr, P pred) {
    if (pr - pl == 1)
      return pred(_acc + (tree[p2].info - tree[p1].info)) ? pr : pl;
    Info diff = tree[tree[p2].ls].info - tree[tree[p1].ls].info;
    if (pred(_acc + diff)) {
      _acc = _acc + diff;
      return bsearch_(tree[p1].rs, tree[p2].rs, MID, pr, pred);
    } else {
      return bsearch_(tree[p1].ls, tree[p2].ls, pl, MID, pred);
    }
  }
#undef MID
};
struct Info {
  int data = 0;
  friend Info operator+(const Info& lhs, const Info& rhs) {
    return {lhs.data + rhs.data};
  }
  friend Info operator-(const Info& lhs, const Info& rhs) {
    return {lhs.data - rhs.data};
  }
};
#line 8 "test/ds/pssgt2.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  vector<int> a(n), dc(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    dc[i] = a[i];
  }
  sort(ALL(dc)), dc.erase(unique(ALL(dc)), dc.end());
  int N = dc.size();
  map<int, int> mp;
  for (int i = 0; i < N; i++) {
    mp[dc[i]] = i;
  }
  for (auto& x : a) {
    x = mp[x];
  }
  SegTree<Info> sgt(N);
  vector<int> buf(N);
  for (int i = 0; i < n; i++) {
    buf[a[i]]++;
    sgt.set(sgt.root.back(), a[i], Info{buf[a[i]]});
  }

  while (q--) {
    int l, r, k;
    cin >> l >> r >> k;
    int qry = sgt.bsearch(sgt.root[l], sgt.root[r],
                          [&](Info x) { return x.data <= k; });
    cout << dc[qry] << "\n";
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_zero_00	AC	6 ms	4 MB
g++	dense_large_a_00	AC	46 ms	4 MB
g++	dense_small_a_00	AC	41 ms	4 MB
g++	example_00	AC	6 ms	4 MB
g++	max_random_00	AC	644 ms	66 MB
g++	max_random_01	AC	658 ms	65 MB
g++	max_random_02	AC	653 ms	66 MB
g++	max_random_03	AC	638 ms	65 MB
g++	max_random_04	AC	657 ms	66 MB
g++	random_00	AC	377 ms	61 MB
g++	random_01	AC	429 ms	63 MB
g++	random_02	AC	139 ms	20 MB
g++	random_03	AC	233 ms	63 MB
g++	random_04	AC	65 ms	8 MB
g++	small_00	AC	6 ms	4 MB
g++	small_01	AC	5 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	6 ms	4 MB
g++	small_05	AC	6 ms	4 MB
g++	small_06	AC	5 ms	4 MB
g++	small_07	AC	5 ms	4 MB
g++	small_08	AC	5 ms	4 MB
g++	small_09	AC	5 ms	4 MB

Back to top page