test/verify/yosupo-range-kth-smallest-3.test.cpp

• View this file on GitHub
• Last update: 2024-08-10 03:11:07+09:00
• Problem: https://judge.yosupo.jp/problem/range_kth_smallest

Depends on

• structure/class/monoid.hpp
• Persistent Segment Tree (永続セグメント木) (structure/segment-tree/persistent-segment-tree.hpp)
• template/template.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_kth_smallest

#include "../../template/template.hpp"

#include "../../structure/segment-tree/persistent-segment-tree.hpp"

int main() {
  int N, Q;
  cin >> N >> Q;
  vector< int > A(N);
  for(auto& a : A) cin >> a;
  auto xs = A;
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());

  auto f = [](int64 a, int64 b) { return a + b; };
  auto e = []() { return 0ll; };
  auto monoid = LambdaMonoid(f, e);
  PersistentSegmentTree  segCnt(monoid, N);
  vector< decltype(segCnt)::NP > cntNP(xs.size() + 1);
  cntNP[0] = segCnt.build(vector< int64 >(N, 0ll));

  vector< vector< int > > upd(xs.size());;
  for(int i = 0; i < N; i++) {
    A[i] = lower_bound(xs.begin(), xs.end(), A[i]) - xs.begin();
    upd[A[i]].emplace_back(i);
  }
  for(int i = 0; i < xs.size(); i++) {
    auto cntNow = cntNP[i];
    for(auto& j : upd[i]) {
      cntNow = segCnt.set(cntNow, j, 1);
    }
    cntNP[i + 1] = cntNow;
  }
  while(Q--) {
    int l, r, k;
    cin >> l >> r >> k;
    int ok = -1, ng = (int) xs.size() - 1;
    auto check = [&](int p) {
      return segCnt.prod(cntNP[p + 1], l, r) <= k;
    };
    while(ng - ok > 1) {
      int mid = (ok + ng) / 2;
      if(check(mid)) ok = mid;
      else ng = mid;
    }
    cout << xs[ok + 1] << "\n";
  }
}

#line 1 "test/verify/yosupo-range-kth-smallest-3.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_kth_smallest

#line 1 "template/template.hpp"
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif

using namespace std;

using int64 = long long;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << p.first << " " << p.second;
  return os;
}

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

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

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

template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}

template <typename T = int64>
vector<T> make_v(size_t a) {
  return vector<T>(a);
}

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) {
  t = v;
}

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) {
  for (auto &e : t) fill_v(e, v);
}

template <typename F>
struct FixPoint : F {
  explicit FixPoint(F &&f) : F(std::forward<F>(f)) {}

  template <typename... Args>
  decltype(auto) operator()(Args &&...args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
inline decltype(auto) MFP(F &&f) {
  return FixPoint<F>{std::forward<F>(f)};
}
#line 4 "test/verify/yosupo-range-kth-smallest-3.test.cpp"

#line 2 "structure/class/monoid.hpp"

template <typename S2, typename Op, typename E>
struct LambdaMonoid {
  using S = S2;
  S op(const S &a, const S &b) const { return _op(a, b); }

  S e() const { return _e(); }

  LambdaMonoid(Op _op, E _e) : _op(_op), _e(_e) {}

 private:
  Op _op;

  E _e;
};

template <typename Op, typename E>
LambdaMonoid(Op _op, E _e) -> LambdaMonoid<decltype(_e()), Op, E>;

/*
struct Monoid {
  using S = ?;
  static constexpr S op(const S& a, const S& b) {}
  static constexpr S e() {}
};
*/
#line 2 "structure/segment-tree/persistent-segment-tree.hpp"

template <typename Monoid>
struct PersistentSegmentTree {
  using S = typename Monoid::S;
  struct Node {
    S d;
    Node *l, *r;
  };
  using NP = Node *;

 private:
  int n{};
  Monoid m;

  NP merge(NP l, NP r) const { return new Node{m.op(l->d, r->d), l, r}; }

  NP build(int l, int r, const vector<S> &v) const {
    if (l + 1 == r) return new Node{v[l], nullptr, nullptr};
    NP lp = build(l, (l + r) / 2, v);
    NP rp = build((l + r) / 2, r, v);
    return merge(lp, rp);
  }

  NP set(int a, const S &x, NP k, int l, int r) const {
    if (r <= a || a + 1 <= l) {
      return k;
    } else if (a <= l && r <= a + 1) {
      return new Node{x, nullptr, nullptr};
    } else {
      return merge(set(a, x, k->l, l, (l + r) >> 1),
                   set(a, x, k->r, (l + r) >> 1, r));
    }
  }

  NP apply(int a, const S &x, NP k, int l, int r) const {
    if (r <= a || a + 1 <= l) {
      return k;
    } else if (a <= l && r <= a + 1) {
      return new Node{m.op(k->d, x), nullptr, nullptr};
    } else {
      return merge(apply(a, x, k->l, l, (l + r) >> 1),
                   apply(a, x, k->r, (l + r) >> 1, r));
    }
  }

  S prod(int a, int b, NP k, int l, int r) const {
    if (r <= a || b <= l) {
      return m.e();
    } else if (a <= l && r <= b) {
      return k->d;
    } else {
      return m.op(prod(a, b, k->l, l, (l + r) >> 1),
                  prod(a, b, k->r, (l + r) >> 1, r));
    }
  }

 public:
  PersistentSegmentTree() = default;

  explicit PersistentSegmentTree(Monoid m, int n) : m(m), n(n) {}

  NP build(const vector<S> &v) const {
    assert(n == (int)v.size());
    return build(0, n, v);
  }

  NP set(NP t, int k, const S &x) const { return set(k, x, t, 0, n); }

  S get(NP t, int k) const {
    int l = 0, r = n;
    while (l + 1 < r) {
      int p = (l + r) / 2;
      if (k < p) {
        t = t->l;
        r = p;
      } else {
        t = t->r;
        l = p;
      }
    }
    return t->d;
  }

  NP apply(NP t, int k, const S &x) const { return apply(k, x, t, 0, n); }

  S prod(NP t, int a, int b) const { return prod(a, b, t, 0, n); }

  S all_prod(NP t) const { return t->d; }
};
#line 6 "test/verify/yosupo-range-kth-smallest-3.test.cpp"

int main() {
  int N, Q;
  cin >> N >> Q;
  vector< int > A(N);
  for(auto& a : A) cin >> a;
  auto xs = A;
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());

  auto f = [](int64 a, int64 b) { return a + b; };
  auto e = []() { return 0ll; };
  auto monoid = LambdaMonoid(f, e);
  PersistentSegmentTree  segCnt(monoid, N);
  vector< decltype(segCnt)::NP > cntNP(xs.size() + 1);
  cntNP[0] = segCnt.build(vector< int64 >(N, 0ll));

  vector< vector< int > > upd(xs.size());;
  for(int i = 0; i < N; i++) {
    A[i] = lower_bound(xs.begin(), xs.end(), A[i]) - xs.begin();
    upd[A[i]].emplace_back(i);
  }
  for(int i = 0; i < xs.size(); i++) {
    auto cntNow = cntNP[i];
    for(auto& j : upd[i]) {
      cntNow = segCnt.set(cntNow, j, 1);
    }
    cntNP[i + 1] = cntNow;
  }
  while(Q--) {
    int l, r, k;
    cin >> l >> r >> k;
    int ok = -1, ng = (int) xs.size() - 1;
    auto check = [&](int p) {
      return segCnt.prod(cntNP[p + 1], l, r) <= k;
    };
    while(ng - ok > 1) {
      int mid = (ok + ng) / 2;
      if(check(mid)) ok = mid;
      else ng = mid;
    }
    cout << xs[ok + 1] << "\n";
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_zero_00	AC	11 ms	9 MB
g++	dense_large_a_00	AC	79 ms	3 MB
g++	dense_small_a_00	AC	61 ms	4 MB
g++	example_00	AC	5 ms	3 MB
g++	max_random_00	AC	2981 ms	147 MB
g++	max_random_01	AC	2857 ms	147 MB
g++	max_random_02	AC	2821 ms	147 MB
g++	max_random_03	AC	2639 ms	147 MB
g++	max_random_04	AC	2687 ms	147 MB
g++	random_00	AC	1739 ms	92 MB
g++	random_01	AC	2086 ms	109 MB
g++	random_02	AC	937 ms	38 MB
g++	random_03	AC	596 ms	122 MB
g++	random_04	AC	264 ms	12 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	5 ms	4 MB
g++	small_05	AC	5 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
clang++	all_zero_00	AC	12 ms	9 MB
clang++	dense_large_a_00	AC	97 ms	3 MB
clang++	dense_small_a_00	AC	69 ms	4 MB
clang++	example_00	AC	5 ms	3 MB
clang++	max_random_00	AC	2738 ms	147 MB
clang++	max_random_01	AC	2677 ms	146 MB
clang++	max_random_02	AC	2579 ms	147 MB
clang++	max_random_03	AC	2730 ms	147 MB
clang++	max_random_04	AC	2683 ms	147 MB
clang++	random_00	AC	1648 ms	92 MB
clang++	random_01	AC	1800 ms	109 MB
clang++	random_02	AC	792 ms	38 MB
clang++	random_03	AC	541 ms	122 MB
clang++	random_04	AC	259 ms	12 MB
clang++	small_00	AC	6 ms	4 MB
clang++	small_01	AC	5 ms	4 MB
clang++	small_02	AC	5 ms	4 MB
clang++	small_03	AC	5 ms	3 MB
clang++	small_04	AC	5 ms	4 MB
clang++	small_05	AC	5 ms	4 MB
clang++	small_06	AC	5 ms	4 MB
clang++	small_07	AC	5 ms	4 MB
clang++	small_08	AC	5 ms	4 MB
clang++	small_09	AC	5 ms	3 MB

Back to top page