TJOI2016 sort

#include <cstdio>

#define DEBUG() // do {debug(root); LOG("\n"); } while (false)
#define LOG(FMT...) // fprintf(stderr, FMT)

using namespace std;

struct node {
    int l, r, d, lazy;
    node *ls, *rs;
};

const int N = 100010;

int n, m, q;
int a[N];
bool op[N];
int opl[N], opr[N];
node* root;

node* build(int l, int r);
void part(node* p, int x);
int query(node* p, int l, int r);
void change(node* p, int l, int r, int x);
void push_down(node* p);
int get_d(node* p);
void debug(node* p);

bool pred(int x);

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d%d", &op[i], &opl[i], &opr[i]);
    scanf("%d", &q);

    root = build(1, n);

    int l = 1, r = n, mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (pred(mid))
            l = mid + 1;
        else
            r = mid;
    }
    printf("%d\n", l);

//  while (getchar());

    return 0;
}

node* build(int l, int r) {
    static node pool[N << 1];
    static node* pc = pool;
    node* p = pc;
    ++pc;
    p->l = l;
    p->r = r;
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    p->ls = build(l, mid);
    p->rs = build(mid + 1, r);
    return p;
}

void part(node* p, int x) {
    p->lazy = 2;
    if (p->l == p->r) {
        p->d = a[p->l] > x;
        return;
    }
    part(p->ls, x);
    part(p->rs, x);
    p->d = p->ls->d + p->rs->d;
}

inline bool pred(int x) {
    part(root, x);
    int cnt;
    DEBUG();
    for (int i = 1; i <= m; ++i) {
        LOG("[INFO]: %d %d %d\n", op[i], opl[i], opr[i]);
        cnt = query(root, opl[i], opr[i]);
        if (op[i]) {
            change(root, opl[i], opl[i] + cnt - 1, 1);
            change(root, opl[i] + cnt, opr[i], 0);
        } else {
            change(root, opl[i], opr[i] - cnt, 0);
            change(root, opr[i] - cnt + 1, opr[i], 1);
        }
        DEBUG();
    }
    return query(root, q, q);
}

int query(node* p, int l, int r) {
    if (p->l == l && p->r == r)
        return get_d(p);
    push_down(p);
    if (r <= p->ls->r)
        return query(p->ls, l, r);
    if (l >= p->rs->l)
        return query(p->rs, l, r);
    return query(p->ls, l, p->ls->r) +
           query(p->rs, p->rs->l, r);
}

void change(node* p, int l, int r, int x) {
    if (l > r)
        return;
    if (p->l == l && p->r == r) {
        p->lazy = x;
        return;
    }
    push_down(p);
    if (r <= p->ls->r)
        change(p->ls, l, r, x);
    else if (l >= p->rs->l)
        change(p->rs, l, r, x);
    else {
        change(p->ls, l, p->ls->r, x);
        change(p->rs, p->rs->l, r, x);
    }
    p->d = get_d(p->ls) + get_d(p->rs);
}

inline void push_down(node* p) {
    if (p->lazy == 2)
        return;
    p->ls->lazy = p->rs->lazy = p->lazy;
    p->d = p->lazy ? (p->r - p->l + 1) : 0;
    p->lazy = 2;
}

inline int get_d(node* p) {
    if (p->lazy == 2)
        return p->d;
    return p->lazy ? (p->r - p->l + 1) : 0;
}

void debug(node* p) {
    if (p->l == p->r) {
        LOG("%2d", get_d(p));
        return;
    }
    push_down(p);
    debug(p->ls);
    debug(p->rs);
}