权值线段树套序列线段树
$O(n\log^2n)$ 的做法

#include <bits/stdc++.h>
using namespace std;
#define N 50005
#define id(x) lower_bound(b + 1, b + len + 1, x) - b
int n, RT, len, m;
int a[N], b[N << 1];
struct ValSegT
{
#define mid ((l + r) >> 1)
    int rt[N << 2], ls[N << 2], rs[N << 2], tot;
    struct PosSegT
    {
        int tot, tr[N * 200], ls[N * 200], rs[N * 200];
        void upd(int &pos, int l, int r, int p, int v)
        {
            if (!pos) pos = ++tot;
            tr[pos] += v;
            if (l == r) return;
            if (p <= mid) upd(ls[pos], l, mid, p, v);
            if (p > mid) upd(rs[pos], mid + 1, r, p, v);
        }
        int qry(int pos, int l, int r, int L, int R)
        {
            if (L <= l && r <= R) return tr[pos];
            if (R <= mid) return qry(ls[pos], l, mid, L, R);
            if (L > mid) return qry(rs[pos], mid + 1, r, L, R);
            return qry(ls[pos], l, mid, L, mid) + qry(rs[pos], mid + 1, r, mid + 1, R);
        }
    } T;
    void upd(int &pos, int l, int r, int p, int v, int op)
    {
        if (!pos) pos = ++tot;
        T.upd(rt[pos], 1, n, p, op);
        if (l == r) return;
        if (v <= mid) upd(ls[pos], l, mid, p, v, op);
        if (v > mid) upd(rs[pos], mid + 1, r, p, v, op);
    }
    int kth(int pos, int l, int r, int _L, int _R, int k)
    {
        if (l == r) return l;
        int t = T.qry(rt[ls[pos]], 1, n, _L, _R);
        if (t >= k) return kth(ls[pos], l, mid, _L, _R, k);
        return kth(rs[pos], mid + 1, r, _L, _R, k - t);
    }
    int rnk(int pos, int l, int r, int L, int R, int _L, int _R)
    {
        if (L > R) return 0;
        if (L <= l && r <= R) return T.qry(rt[pos], 1, n, _L, _R);
        if (R <= mid) return rnk(ls[pos], l, mid, L, R, _L, _R);
        if (L > mid) return rnk(rs[pos], mid + 1, r, L, R, _L, _R);
        return rnk(ls[pos], l, mid, L, mid, _L, _R) + rnk(rs[pos], mid + 1, r, mid + 1, R, _L, _R);
    }
    int pre(int x, int _L, int _R)
    {
        int r = rnk(RT, 1, len, 1, x - 1, _L, _R) + 1;
        if (r == 1) return -2147483647;
        return kth(RT, 1, len, _L, _R, r - 1);
    }
    int suc(int x, int _L, int _R)
    {
        int r = rnk(RT, 1, len, 1, x, _L, _R);
        if (r == _R - _L + 1) return 2147483647;
        return kth(RT, 1, len, _L, _R, r + 1);
    }
} T;
struct ask
{
    int op, a, b, c;
} p[N];
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    for (int i = 1; i <= m; i++)
    {
        cin >> p[i].op >> p[i].a >> p[i].b;
        if (p[i].op != 3) cin >> p[i].c;
        if (p[i].op == 3) b[i + n] = p[i].b;
        if (p[i].op == 1 || p[i].op == 4 || p[i].op == 5) b[i + n] = p[i].c;
    }
    sort(b + 1, b + n + m + 1);
    len = unique(b + 1, b + n + m + 1) - b - 1;
    for (int i = 1; i <= n; i++) T.upd(RT, 1, len, i, id(a[i]), 1);
    for (int i = 1; i <= m; i++)
    {
        if (p[i].op == 1)
            cout << T.rnk(RT, 1, len, 1, id(p[i].c) - 1, p[i].a, p[i].b) + 1;
        if (p[i].op == 2) cout << b[T.kth(RT, 1, len, p[i].a, p[i].b, p[i].c)];
        if (p[i].op == 3)
        {
            T.upd(RT, 1, len, p[i].a, id(a[p[i].a]), -1);
            a[p[i].a] = p[i].b;
            T.upd(RT, 1, len, p[i].a, id(a[p[i].a]), 1);
        }
        if (p[i].op == 4) cout << b[T.pre(id(p[i].c), p[i].a, p[i].b)];
        if (p[i].op == 5) cout << b[T.suc(id(p[i].c), p[i].a, p[i].b)];
        if (p[i].op != 3) cout << '\n';
    }
    return 0;
}