test/data-structure/merge-sort-tree/yosupo-Range-Kth-Smallest.test.cpp

• View this file on GitHub
• Last update: 2023-07-01 16:07:45+08:00
• Problem: https://judge.yosupo.jp/problem/range_kth_smallest

Depends on

• Merge Sort Tree (library/data-structure/merge-sort-tree.hpp)

Code

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

#include <iostream>

#include <vector>

#include <algorithm>

#include "../../../library/data-structure/merge-sort-tree.hpp"

using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	auto xs = a;
	sort(xs.begin(), xs.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	for(int i = 0; i < n; i++) {
		a[i] = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
	}
	merge_sort_tree<int> tree(a);
	while(q--) {
		int l, r, k;
		cin >> l >> r >> k;
		k++;
		int ok = 0, ng = (int) xs.size();
		while(ng - ok > 1) {
			int mid = (ok + ng) / 2;
			if(tree.count_less(l, r, mid) < k) {
				ok = mid;
			} else {
				ng = mid;
			}
		}
		cout << xs[ok] << "\n";
	}
	return 0;
}

#line 1 "test/data-structure/merge-sort-tree/yosupo-Range-Kth-Smallest.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_kth_smallest"

#include <iostream>

#include <vector>

#include <algorithm>

#line 4 "library/data-structure/merge-sort-tree.hpp"

namespace felix {

template<class T>
struct merge_sort_tree {
public:
	merge_sort_tree() : n(0) {}
	explicit merge_sort_tree(const std::vector<T>& val) : n(val.size()), tree(val.size() * 2) {
		for(int i = 0; i < n; i++) {
			tree[n + i] = {val[i]};
		}
		for(int i = n - 1; i >= 0; i--) {
			std::merge(tree[2 * i].begin(), tree[2 * i].end(), tree[2 * i + 1].begin(), tree[2 * i + 1].end(), std::back_inserter(tree[i]));
		}
	}

	int count_less(int l, int r, T x) const {
		int ans = 0;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) {
				ans += std::lower_bound(tree[l].begin(), tree[l].end(), x) - tree[l].begin();
				l++;
			}
			if(r & 1) {
				r--;
				ans += std::lower_bound(tree[r].begin(), tree[r].end(), x) - tree[r].begin();
			}
		}
		return ans;
	}

	int count_less_equal(int l, int r, T x) const {
		int ans = 0;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) {
				ans += std::upper_bound(tree[l].begin(), tree[l].end(), x) - tree[l].begin();
				l++;
			}
			if(r & 1) {
				r--;
				ans += std::upper_bound(tree[r].begin(), tree[r].end(), x) - tree[r].begin();
			}
		}
		return ans;
	}

	int count_greater(int l, int r, T x) const {
		return r - l - count_less_equal(l, r, x);
	}

	int count_greater_equal(int l, int r, T x) const {
		return r - l - count_less(l, r, x);
	}

private:
	int n;
	std::vector<std::vector<T>> tree;
};

} // namespace felix

#line 7 "test/data-structure/merge-sort-tree/yosupo-Range-Kth-Smallest.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	auto xs = a;
	sort(xs.begin(), xs.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	for(int i = 0; i < n; i++) {
		a[i] = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
	}
	merge_sort_tree<int> tree(a);
	while(q--) {
		int l, r, k;
		cin >> l >> r >> k;
		k++;
		int ok = 0, ng = (int) xs.size();
		while(ng - ok > 1) {
			int mid = (ok + ng) / 2;
			if(tree.count_less(l, r, mid) < k) {
				ok = mid;
			} else {
				ng = mid;
			}
		}
		cout << xs[ok] << "\n";
	}
	return 0;
}

Back to top page