#include #include #include #include using namespace std; template class LiteralSegmentTree { protected: vector> containers; public: constexpr LiteralSegmentTree(const vector& 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&& 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(vector(n, default_value)) { } constexpr LiteralSegmentTree(const size_t n, const T initial_value) : LiteralSegmentTree(vector(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 using DefaultMaxPicker = decltype([](const T a, const T b) { return std::max(a, b); }); template::lowest()> class MaxSegmentTree : public LiteralSegmentTree { public: constexpr MaxSegmentTree(const vector& initializer) : LiteralSegmentTree(initializer) { } constexpr MaxSegmentTree(vector&& initializer) : LiteralSegmentTree(initializer) { } template constexpr MaxSegmentTree(const Args... args) : LiteralSegmentTree(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 type(Q); vector x(Q); for (i = 0; i != Q; ++i) cin >> type[i] >> x[i]; MaxSegmentTree> 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; }