来之不易的AC

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
const int MAXN = 1e5 + 10;
struct Node {
    int sum;
    int cover;  
} tree[4 * MAXN];

void build(int node, int l, int r, const vector& data) {

tree[node].cover = -1;
if (l == r) {
    tree[node].sum = data[l];
    return;
}
int mid = (l + r) >> 1;
build(2 * node, l, mid, data);
build(2 * node + 1, mid + 1, r, data);
tree[node].sum = tree[2 * node].sum + tree[2 * node + 1].sum;

}

void push_down(int node, int l, int r) {

if (tree[node].cover != -1) {
    int mid = (l + r) >> 1;
    int left = 2 * node;
    tree[left].cover = tree[node].cover;
    tree[left].sum = (mid - l + 1) * tree[node].cover;
    int right = 2 * node + 1;
    tree[right].cover = tree[node].cover;
    tree[right].sum = (r - mid) * tree[node].cover;
    tree[node].cover = -1;
}

}

void update_range(int node, int l, int r, int ul, int ur, int val) {

if (ur < l || ul > r) return;
if (ul <= l && r <= ur) {
    tree[node].cover = val;
    tree[node].sum = (r - l + 1) * val;
    return;
}
push_down(node, l, r);
int mid = (l + r) >> 1;
update_range(2 * node, l, mid, ul, ur, val);
update_range(2 * node + 1, mid + 1, r, ul, ur, val);
tree[node].sum = tree[2 * node].sum + tree[2 * node + 1].sum;

}

int query_range(int node, int l, int r, int ql, int qr) {

if (qr < l || ql > r) return 0;
if (ql <= l && r <= qr) return tree[node].sum;
push_down(node, l, r);
int mid = (l + r) >> 1;
return query_range(2 * node, l, mid, ql, qr) + query_range(2 * node + 1, mid + 1, r, ql, qr);

}

int main() {

ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m;
cin >> n >> m;

vector<int> arr(n);
for (int i = 0; i < n; ++i) {
    cin >> arr[i];
}

vector<tuple<int, int, int>> ops(m);
for (int i = 0; i < m; ++i) {
    int op, l, r;
    cin >> op >> l >> r;
    ops[i] = make_tuple(op, l - 1, r - 1);
}

int q;
cin >> q;
q--;  

int low = 1, high = n;
int ans = -1;

while (low <= high) {
    int mid = (low + high) >> 1;
    vector<int> bit(n);
    for (int i = 0; i < n; ++i) {
        bit[i] = arr[i] >= mid ? 1 : 0;
    }

    build(1, 0, n - 1, bit);

    for (const auto& op : ops) {
        int type = get<0>(op);
        int l = get<1>(op);
        int r = get<2>(op);
        int sum = query_range(1, 0, n - 1, l, r);
        int len = r - l + 1;

        if (type == 0) { 
            int k = len - sum;
            if (k > 0) {
                update_range(1, 0, n - 1, l, l + k - 1, 0);
            }
            if (sum > 0) {
                update_range(1, 0, n - 1, l + k, r, 1);
            }
        } else { 
            int k = sum;
            if (k > 0) {
                update_range(1, 0, n - 1, l, l + k - 1, 1);
            }
            if (len - k > 0) {
                update_range(1, 0, n - 1, l + k, r, 0);
            }
        }
    }

    int res = query_range(1, 0, n - 1, q, q);
    if (res == 1) {
        ans = mid;
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}
cout << ans << endl;
return 0;

} 保熟