2BTree

#include <climits>
#include <cstdio>
#include <ctime>

#include <algorithm>

#define LOG(FMT...) // fprintf(stderr, FMT)

using namespace std;

struct tre {
    int x, cnt, sz, rnd;
    tre *ls, *rs;
};

struct seg {
    int l, r;
    tre* root;
    seg *ls, *rs;
};

const int N = 50010;

int n, m;
tre *res1, *res2;
seg* root;
int a[N];

int fast_rand();
seg* construct(int l, int r);
tre* create(int x);
int get_cnt(tre* p);
void update(tre* p);
void insert(tre*& p, int x);
void insert(tre*& p, tre* q);
void remove(tre*& p, int x);
void zig(tre*& p);
void zag(tre*& p);
void change(seg* p, int k, int x);
bool remove_x(tre*& p, int x);
int prev(tre* p, int x);
int post(tre* p, int x);
int get_rank(tre* p, int x);
int get_rank(seg* p, int l, int r, int x);
int get_x(int l, int r, int x);
int prev(seg* p, int l, int r, int x);
int post(seg* p, int l, int r, int x);
void out(int x);

int main() {
//  freopen("test.in", "r", stdin);
//  freopen("test.out", "w", stdout);
    int l, r, k, x, op;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    root = construct(1, n);
    while (m--) {
        scanf("%d", &op);
        switch (op) {
        case 1:
            scanf("%d%d%d", &l, &r, &x);
            out(get_rank(root, l, r, x) + 1);
            break;
        case 2:
            scanf("%d%d%d", &l, &r, &k);
            out(get_x(l, r, k - 1));
            break;
        case 3:
            scanf("%d%d", &k, &x);
            change(root, k, x);
            a[k] = x;
            break;
        case 4:
            scanf("%d%d%d", &l, &r, &x);
            out(prev(root, l, r, x));
            break;
        case 5:
            scanf("%d%d%d", &l, &r, &x);
            out(post(root, l, r, x));
            break;
        }
    }
    return 0;
}

inline void remove(tre*& p, int x) {
    if (remove_x(p, x)) {
        if (res1)
            insert(p, res1);
        if (res2)
            insert(p, res2);
    }
}

inline void out(int x) {
    printf("%d\n", x);
}

int get_rank(seg* p, int l, int r, int x) {
    if (p->l == l && p->r == r)
        return get_rank(p->root, x);
    if (r <= p->ls->r)
        return get_rank(p->ls, l, r, x);
    if (l >= p->rs->l)
        return get_rank(p->rs, l, r, x);
    return get_rank(p->ls, l, p->ls->r, x) +
           get_rank(p->rs, p->rs->l, r, x);
}

inline int get_rank(tre* p, int x) {
    int ret = 0;
    while (p)
        if (x <= p->x)
            p = p->ls;
        else {
            ret += p->sz + get_cnt(p->ls);
            p = p->rs;
        }
    return ret;
}

inline tre* create(int x) {
    static tre pool[N << 5];
    static tre* p = pool;
    ++p;
    p->x = x;
    p->cnt = p->sz = 1;
    p->rnd = fast_rand();
    return p;
}

inline void zig(tre*& p) {
    tre* son = p->ls;
    p->ls = son->rs;
    son->rs = p;
    update(p);
    p = son;
    update(p);
}

inline void zag(tre*& p) {
    tre* son = p->rs;
    p->rs = son->ls;
    son->ls = p;
    update(p);
    p = son;
    update(p);
}

inline int get_cnt(tre* p)
{ return p ? p->cnt : 0; }

inline void update(tre* p)
{ p->cnt = p->sz + get_cnt(p->ls) + get_cnt(p->rs); }

void insert(tre*& p, tre* q) {
    if (!p) {
        p = q;
        return;
    }
    if (q->x <= p->x) {
        insert(p->ls, q);
        update(p);
        if (p->ls->cnt < p->cnt)
            zig(p);
    } else {
        insert(p->rs, q);
        update(p);
        if (p->rs->cnt < p->cnt)
            zag(p);
    }
}

void insert(tre*& p, int x) {
    if (!p) {
        p = create(x);
        return;
    }
    if (p->x == x) {
        ++p->sz;
        ++p->cnt;
        return;
    }
    if (x < p->x) {
        insert(p->ls, x);
        update(p);
        if (p->ls->cnt < p->cnt)
            zig(p);
    } else {
        insert(p->rs, x);
        update(p);
        if (p->rs->cnt < p->cnt)
            zag(p);
    }
}

seg* construct(int l, int r) {
    static seg pool[N << 1];
    static int cnt;
    seg* p = pool + cnt;
    ++cnt;
    p->l = l;
    p->r = r;
    for (int i = l; i <= r; ++i)
        insert(p->root, a[i]);
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    p->ls = construct(l, mid);
    p->rs = construct(mid + 1, r);
    return p;
}

inline int fast_rand() {
    static int x = time(NULL), y = x << 4, z = x >> 2, t;
    x ^= x << 4;
    x ^= x >> 2;
    t = x ^ y ^ z;
    z = y;
    y = x;
    x = t;
    return t;
}

inline int get_x(int l, int r, int x) {
    int lx = -100000000, rx = 100000000, mid;
    while (lx < rx) {
        mid = (lx + rx) >> 1;
        if (get_rank(root, l, r, mid) <= x)
            lx = mid + 1;
        else
            rx = mid;
    }
    return lx - 1;
}

inline bool remove_x(tre*& p, int x) {
    if (!p)
        return false;
    if (p->x == x) {
        --p->sz;
        --p->cnt;
        if (!p->sz) {
            res1 = p->ls;
            res2 = p->rs;
            p = NULL;
            return true;
        }
        return false;
    }
    if (x < p->x)
        remove(p->ls, x);
    else
        remove(p->rs, x);
    update(p);
    return false;
}

inline void change(seg* p, int k, int x) {
    while (p) {
        remove(p->root, a[k]);
        insert(p->root, x);
        if (p->l == p->r)
            return;
        if (k <= p->ls->r)
            p = p->ls;
        else
            p = p->rs;
    }
}

inline int prev(tre* p, int x) {
    int ret = -INT_MAX;
    while (p)
        if (p->x < x) {
            ret = max(ret, p->x);
            p = p->rs;
        } else
            p = p->ls;
    return ret;
}

inline int post(tre* p, int x) {
    int ret = INT_MAX;
    while (p)
        if (p->x > x) {
            ret = min(ret, p->x);
            p = p->ls;
        } else
            p = p->rs;
    return ret;
}

int prev(seg* p, int l, int r, int x) {
    if (p->l == l && p->r == r)
        return prev(p->root, x);
    if (r <= p->ls->r)
        return prev(p->ls, l, r, x);
    if (l >= p->rs->l)
        return prev(p->rs, l, r, x);
    return max(prev(p->ls, l, p->ls->r, x),
               prev(p->rs, p->rs->l, r, x));
}

int post(seg* p, int l, int r, int x) {
    if (p->l == l && p->r == r)
        return post(p->root, x);
    if (r <= p->ls->r)
        return post(p->ls, l, r, x);
    if (l >= p->rs->l)
        return post(p->rs, l, r, x);
    return min(post(p->ls, l, p->ls->r, x),
               post(p->rs, p->rs->l, r, x));
}