結果

問題 No.3198 Monotonic Query
ユーザー elphe
提出日時 2025-07-11 23:23:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 50 ms / 3,000 ms
コード長 6,703 bytes
コンパイル時間 1,210 ms
コンパイル使用メモリ 97,804 KB
実行使用メモリ 10,724 KB
最終ジャッジ日時 2025-07-12 10:56:19
合計ジャッジ時間 3,793 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdint>
#include <vector>
#include <limits>

using namespace std;

template<typename T, class Picker, T default_value> class LiteralSegmentTree
{
protected:
	vector<vector<T>> containers;

public:
	constexpr LiteralSegmentTree(const vector<T>& initializer)
	{
		containers.clear();

		if (initializer.size() == 0) return;
		else if (initializer.size() == 1) { containers.emplace_back(1, initializer[0]); return; }

		size_t l = 0, r = 30;
		while (l + 1 < r)
		{
			const auto c = (l + r) >> 1;
			if (((size_t)1 << c) < initializer.size())
				l = c;
			else
				r = c;
		}

		containers.emplace_back((size_t)1 << r);

		size_t i;
		for (i = 0; i != initializer.size(); ++i)
			containers[0][i] = initializer[i];
		for (; i != ((size_t)1 << r); ++i)
			containers[0][i] = default_value;

		for (--r; r != 0; --r)
		{
			containers.emplace_back((size_t)1 << r);
			for (i = 0; i != ((size_t)1 << r); ++i)
				containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
		}
		containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
	}

	constexpr LiteralSegmentTree(vector<T>&& initializer)
	{
		containers.clear();

		if (initializer.size() == 0) return;

		size_t l = 0, r = 30;
		while (l + 1 < r)
		{
			const auto c = (l + r) >> 1;
			if (((size_t)1 << c) < initializer.size())
				l = c;
			else
				r = c;
		}

		containers.emplace_back(initializer);
		containers[0].resize((size_t)1 << r, default_value);

		size_t i;
		for (--r; r != 0; --r)
		{
			containers.emplace_back((size_t)1 << r);
			for (i = 0; i != ((size_t)1 << r); ++i)
				containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
		}
		containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
	}

	constexpr LiteralSegmentTree(const size_t n) : LiteralSegmentTree<T, Picker, default_value>(vector<T>(n, default_value)) { }
	constexpr LiteralSegmentTree(const size_t n, const T initial_value) : LiteralSegmentTree<T, Picker, default_value>(vector<T>(n, initial_value)) { }

	virtual constexpr T operator[](size_t index) const noexcept { return containers[0][index]; }

	constexpr size_t size() const noexcept { return containers[0].size(); }
	constexpr size_t layer() const noexcept { return containers.size(); }

	virtual constexpr T update(size_t index, const T value) noexcept
	{
		containers[0][index] = value;

		index >>= 1;
		for (size_t i = 1; i != containers.size(); ++i, index >>= 1)
			containers[i][index] = Picker()(containers[i - 1][index << 1], containers[i - 1][(index << 1) | 1]);

		return value;
	}

	virtual constexpr T range_pick_up(size_t first_index, size_t end_index) const noexcept
	{
		if (containers.size() == 0 || end_index > containers[0].size()) return default_value;

		T ret = default_value;
		for (size_t cur_layer = 0; first_index < end_index; first_index >>= 1, end_index >>= 1, ++cur_layer)
		{
			if (first_index & 1)
				ret = Picker()(ret, containers[cur_layer][first_index]), ++first_index;
			if (end_index & 1)
				ret = Picker()(ret, containers[cur_layer][end_index - 1]);
		}

		return ret;
	}
};

template<typename T> using DefaultMaxPicker = decltype([](const T a, const T b) { return std::max<T>(a, b); });

template<typename T, class MaxPicker, T default_value = numeric_limits<T>::lowest()>
class MaxSegmentTree : public LiteralSegmentTree<T, MaxPicker, default_value>
{
public:
	constexpr MaxSegmentTree(const vector<T>& initializer) : LiteralSegmentTree<T, MaxPicker, default_value>(initializer) { }
	constexpr MaxSegmentTree(vector<T>&& initializer) : LiteralSegmentTree<T, MaxPicker, default_value>(initializer) { }
	template<typename... Args> constexpr MaxSegmentTree(const Args... args) : LiteralSegmentTree<T, MaxPicker, default_value>(args...) { }

	constexpr size_t leftest_above(const size_t first, const size_t last, const T limit) const noexcept
	{
		if (this->containers.size() == 0) return 0;

		size_t cur_layer, cur_index;

		size_t candidate_layer = this->containers.size(), candidate_index;
		size_t first_temp = first, last_temp = last;
		for (cur_layer = 0; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
		{
			if (first_temp & 1)
			{
				if (this->containers[cur_layer][first_temp] >= limit)
					break;
				++first_temp;
			}
			if (last_temp & 1)
			{
				if (this->containers[cur_layer][last_temp - 1] >= limit)
					candidate_layer = cur_layer, candidate_index = last_temp - 1;
				//--last_temp;
			}
		}

		if (first_temp != last_temp) cur_index = first_temp;
		else if (candidate_layer == this->containers.size()) return this->containers[0].size();
		else cur_layer = candidate_layer, cur_index = candidate_index;

		while (cur_layer != 0)
		{
			--cur_layer, cur_index <<= 1;
			if (this->containers[cur_layer][cur_index] < limit)
				cur_index |= 1;
		}

		return cur_index;
	}

	constexpr size_t rightest_above(const size_t first, const size_t last, const T limit) const noexcept
	{
		if (this->containers.size() == 0) return 0;

		size_t cur_layer, cur_index;

		size_t candidate_layer = this->containers.size(), candidate_index;
		size_t first_temp = first, last_temp = last;
		for (cur_layer = 0; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
		{
			if (last_temp & 1)
			{
				if (this->containers[cur_layer][last_temp - 1] >= limit)
					break;
				//--last_temp;
			}
			if (first_temp & 1)
			{
				if (this->containers[cur_layer][first_temp] >= limit)
					candidate_layer = cur_layer, candidate_index = first_temp;
				++first_temp;
			}
		}

		if (first_temp != last_temp) cur_index = last_temp - 1;
		else if (candidate_layer == this->containers.size()) return this->containers[0].size();
		else cur_layer = candidate_layer, cur_index = candidate_index;

		while (cur_layer != 0)
		{
			--cur_layer, cur_index <<= 1;
			if (this->containers[cur_layer][cur_index | 1] >= limit)
				cur_index |= 1;
		}

		return cur_index;
	}
};

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	
	uint_fast32_t Q, i;
	std::cin >> Q;
	vector<char> type(Q);
	vector<uint_fast32_t> x(Q);
	for (i = 0; i != Q; ++i)
		cin >> type[i] >> x[i];

	MaxSegmentTree<uint_fast32_t, DefaultMaxPicker<uint_fast32_t>> mst(Q);
	uint_fast32_t mst_count = 0;
	for (i = 0; i != Q; ++i)
		switch (type[i])
		{
		case '1':
			mst.update(mst_count, x[i]), ++mst_count;
			break;

		case '2':
			std::cout << mst.range_pick_up(mst_count - x[i], mst_count) << '\n';
			break;
		}

	return 0;
}
0