meaning of the title

Title Link

Sol

Divine binary Orz

First of all, the answer is divided into two parts, i.e. if the location of the inquiry is $x $, the one with $> = x $is regarded as $1 $, and the one with $< x $is regarded as $0$

Simulate the formed $0 / 1 $sequence and maintain the line tree.

Finally, narrow the range of answers according to the number of positions

It's hard to think about the monotony of this question, but it's quite obvious to prove it. Consider that if the final value of $x $corresponds to $1 $, then the final value of $< x $corresponds to $1$

#include<bits/stdc++.h>
#define Pair pair<int, int> 
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int MAXN = 4e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, Q;
int a[MAXN], b[MAXN], opt[MAXN], L[MAXN], R[MAXN];
#define ls k << 1
#define rs k << 1 | 1
struct Node {
    int l, r, siz, tag, cnt[2];
}T[MAXN];   
Pair operator + (const Pair &a, const Pair &b) {
    return MP(a.fi + b.fi, a.se + b.se);
}
void update(int k) {
    for(int i = 0; i <= 1; i++) T[k].cnt[i] = T[ls].cnt[i] + T[rs].cnt[i];
}
void ps(int k, int val) {
    T[k].cnt[0] = T[k].cnt[1] = 0;
    T[k].cnt[val] = T[k].siz;
    T[k].tag = val;
}
void pushdown(int k) {
    if(T[k].tag == -1) return ;
    ps(ls, T[k].tag); ps(rs, T[k].tag);
    T[k].tag = -1;
}
void Build(int k, int ll, int rr) {
    T[k].l = ll; T[k].r = rr; T[k].siz = rr - ll + 1; T[k].tag = -1; T[k].cnt[0] = T[k].cnt[1] = 0;
    if(ll == rr) {T[k].cnt[b[ll]]++; return ;}
    int mid = ll + rr >> 1;
    Build(ls, ll, mid); Build(rs, mid + 1, rr);
    update(k);
}
Pair Query(int k, int ll, int rr) {
    if(ll <= T[k].l && T[k].r <= rr) return MP(T[k].cnt[0], T[k].cnt[1]);
    int mid = T[k].l + T[k].r >> 1;
    pushdown(k);
    if(ll > mid) return Query(rs, ll, rr);
    if(rr <= mid) return Query(ls, ll, rr);
    return Query(ls, ll, rr) + Query(rs, ll, rr);
}
void Mem(int k, int ll, int rr, int val) {
    if(ll <= T[k].l && T[k].r <= rr) {
        ps(k, val); return ;
    }
    pushdown(k);
    int mid = T[k].l + T[k].r >> 1;
    if(ll <= mid) Mem(ls, ll, rr, val);
    if(rr >  mid) Mem(rs, ll, rr, val);
    update(k);
}
int Point(int k, int pos) {
    if(T[k].l == T[k].r) {
        if(T[k].cnt[1]) return 1;
        else return 0;
    }
    pushdown(k);
    int mid = T[k].l + T[k].r >> 1;
    if(pos <= mid) return Point(ls, pos);
    else return Point(rs, pos);
}
void dfs(int k) {
    if(T[k].l == T[k].r) {
        if(T[k].cnt[1]) printf("1 ");
        else printf("0 ");
        return ;
    }
    pushdown(k);
    dfs(ls); dfs(rs);
}
bool check(int val) {
    for(int i = 1; i <= N; i++) b[i] = (a[i] >= val);
    Build(1, 1, N);
    //dfs(1); puts("");
    for(int i = 1; i <= M; i++) {
        Pair now = Query(1, L[i], R[i]);
        if(opt[i] == 0) Mem(1, L[i], L[i] + now.fi - 1, 0), Mem(1, L[i] + now.fi, R[i], 1);
        else Mem(1, L[i], L[i] + now.se - 1, 1), Mem(1, L[i] + now.se, R[i], 0);
    //  dfs(1); puts("");
    }
    return Point(1, Q);
}
main() {
    N = read(); M = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    for(int i = 1; i <= M; i++) opt[i] = read(), L[i] = read(), R[i] = read();
    Q = read();
    int l = 1, r = N, ans = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    printf("%d", ans);
}