lessons/参考实现/08-高级线段树与树状数组/HYSBZ-4552.cpp

#include <iostream>
#include <map>
#include <vector>
using namespace std;
struct Node { int left = 0, right = 0, count = 0; };
struct Block { int right, root; bool descending; };
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, operations; cin >> n >> operations;
    vector<Node> tree(1); tree.reserve(static_cast<size_t>(n + 2 * operations) * 22);
    auto new_node = [&] { tree.push_back({}); return static_cast<int>(tree.size()) - 1; };
    auto insert = [&](auto &&self, int u, int l, int r, int p) -> int {
        if (!u) u = new_node(); ++tree[u].count;
        if (l < r) { int mid = (l + r) / 2; if (p <= mid) tree[u].left = self(self, tree[u].left, l, mid, p); else tree[u].right = self(self, tree[u].right, mid + 1, r, p); }
        return u;
    };
    auto pull = [&](int u) { tree[u].count = tree[tree[u].left].count + tree[tree[u].right].count; };
    auto split_small = [&](auto &&self, int u, int k, int l, int r) -> pair<int,int> {
        if (!u) return {0, 0};
        if (k == 0) return {0, u};
        if (k == tree[u].count) return {u, 0};
        int a = new_node(), b = new_node(), mid = (l + r) / 2;
        int left_count = tree[tree[u].left].count;
        if (k <= left_count) {
            auto [x, y] = self(self, tree[u].left, k, l, mid);
            tree[a].left = x; tree[b].left = y; tree[b].right = tree[u].right;
        } else {
            auto [x, y] = self(self, tree[u].right, k - left_count, mid + 1, r);
            tree[a].left = tree[u].left; tree[a].right = x; tree[b].right = y;
        }
        pull(a); pull(b); return {a, b};
    };
    auto merge = [&](auto &&self, int a, int b, int l, int r) -> int {
        if (!a) return b; if (!b) return a;
        if (l < r) { int mid = (l + r) / 2; tree[a].left = self(self, tree[a].left, tree[b].left, l, mid); tree[a].right = self(self, tree[a].right, tree[b].right, mid + 1, r); }
        tree[a].count += tree[b].count; return a;
    };
    auto kth = [&](auto &&self, int u, int l, int r, int k) -> int {
        if (l == r) return l; int mid = (l + r) / 2, left_count = tree[tree[u].left].count;
        return k <= left_count ? self(self, tree[u].left, l, mid, k) : self(self, tree[u].right, mid + 1, r, k - left_count);
    };
    map<int, Block> blocks;
    for (int i = 1, value; i <= n; ++i) { cin >> value; blocks[i] = {i, insert(insert, 0, 1, n, value), false}; }
    auto split_position = [&](int position) {
        if (position > n) return blocks.end();
        auto it = prev(blocks.upper_bound(position));
        if (it->first == position) return it;
        int l = it->first, r = it->second.right, take = position - l, total = r - l + 1;
        int first, second;
        if (!it->second.descending) tie(first, second) = split_small(split_small, it->second.root, take, 1, n);
        else tie(second, first) = split_small(split_small, it->second.root, total - take, 1, n);
        bool direction = it->second.descending; it->second = {position - 1, first, direction};
        return blocks.emplace(position, Block{r, second, direction}).first;
    };
    while (operations--) {
        int op, l, r; cin >> op >> l >> r;
        auto finish = split_position(r + 1), begin = split_position(l);
        int root = 0;
        for (auto it = begin; it != finish; ++it) root = merge(merge, root, it->second.root, 1, n);
        blocks.erase(begin, finish); blocks[l] = {r, root, op == 1};
    }
    int q; cin >> q; auto it = prev(blocks.upper_bound(q));
    int offset = q - it->first, size = it->second.right - it->first + 1;
    cout << kth(kth, it->second.root, 1, n, it->second.descending ? size - offset : offset + 1) << '\n';
}