做数据结构一定要平\((fo)\)心\((de)\)静\((yi)\)气\((pi)\)。。。不然会四处出锅的\(QAQ\)

写法：线段树套平衡树，\(O(Nlog^3N)\)。五个操作如果是对于整个区间的，那么就是平衡树板子题。现在既然是放在子区间上的，那么套一个线段树就好啦~

#include 
    
     using namespace std;const int N = 50000 + 5;const int INF = 1e8 + 5;#define ls (p << 1)#define rs (p << 1 | 1)#define mid ((l + r) >> 1)int n, m, tot, arr[N];struct FHQ_Node {    int w, lc, rc, sz, rd;}t[N << 8];struct FHQ_Treap {        int rt;        int NewNode (int w) {        t[++tot] = FHQ_Node {w, 0, 0, 1, rand ()};        return tot;    }        void push_up (int p) {        t[p].sz = 1;        if (t[p].lc) t[p].sz += t[t[p].lc].sz;        if (t[p].rc) t[p].sz += t[t[p].rc].sz;    }        void split (int now, int &A, int &B, int w) {        if (now == 0) {            A = B = 0; return;        }        if (t[now].w <= w) {            A = now; split (t[now].rc, t[A].rc, B, w);        } else {            B = now; split (t[now].lc, A, t[B].lc, w);        }        push_up (now);    }        int merge (int A, int B) {        if (A * B == 0) {            return A + B;        }        if (t[A].rd < t[B].rd) {            t[A].rc = merge (t[A].rc, B);             push_up (A); return A;        } else {            t[B].lc = merge (A, t[B].lc);            push_up (B); return B;        }    }        int x, y, z;        void Insert (int w) {        split (rt, x, y, w);        rt = merge (x, merge (NewNode (w), y));//      cout << "rt = " << rt << endl;    }        void Delete (int w) {        split (rt, x, y, w - 1);        split (y, y, z, w);        y = merge (t[y].lc, t[y].rc);        rt = merge (x, merge (y, z));    }        int pre (int w) {        split (rt, x, y, w - 1);        int p = x;        if (p == 0) {            return -0x7fffffff;        }        while (t[p].rc != 0) {            p = t[p].rc;        }        rt = merge (x, y);        return t[p].w;    }        int nxt (int w) {        split (rt, x, y, w);        int p = y;        if (p == 0) {            return +0x7fffffff;        }        while (t[p].lc != 0) {            p = t[p].lc;        }        rt = merge (x, y);        return t[p].w;    }        void print (int p) {        if (t[p].lc) print (t[p].lc);//      cout << "p = " << p << " w = " << t[p].w << " sz = " << t[p].sz << endl;        if (t[p].rc) print (t[p].rc);    }        int rank (int w) {        split (rt, x, y, w - 1);        int ret = t[x].sz + 1;        rt = merge (x, y); //      print (rt); cout << endl;        return ret;    }};struct Segment_Tree {        FHQ_Treap tree[N << 2];        void modify (int pos, int wpre, int wnew, int l = 1, int r = n, int p = 1) {//      cout << "p = " << p << endl;        if (wpre != -1) {tree[p].Delete (wpre);/*cout << "tree[" << p << "].Delete (" << wpre << ");" << endl;*/}        if (wnew != -1) {tree[p].Insert (wnew);/*cout << "tree[" << p << "].Insert (" << wnew << ");" << endl;*/}        if (l == r) return;        if (pos <= mid) {            modify (pos, wpre, wnew, l, mid + 0, ls);        } else {            modify (pos, wpre, wnew, mid + 1, r, rs);        }    }        int tot, sta[N];        void get_segment (int nl, int nr, int l = 1, int r = n, int p = 1) {        if (p == 1) tot = 0;        if (nl <= l && r <= nr) {            sta[++tot] = p; return;        }        if (nl <= mid) get_segment (nl, nr, l, mid + 0, ls);        if (mid < nr) get_segment (nl, nr, mid + 1, r, rs);    }         int rank (int l, int r, int w) {        get_segment (l, r);        int ret = 1;        for (int i = 1; i <= tot; ++i) {//          cout << tree[sta[i]].rank (w) << endl;            ret += (tree[sta[i]].rank (w) - 1);        }//      cout << "val = " << w << " rank = " << ret << endl;        return ret;    }         int kth (int l, int r, int k) {        int lval = 0, rval = INF;//      cout << "k = " << k << endl;        while (lval < rval) {//          getchar ();            int _mid = (lval + rval + 1) >> 1;//          cout << "lval = " << lval << " rval = " << rval << " mid = " << _mid << " rank " << k << " = " << rank (l, r, _mid) << endl;            if (rank (l, r, _mid) <= k) {                lval = _mid;            } else {                rval = _mid - 1;            }        }        return lval;    }        int pre (int l, int r, int w) {        get_segment (l, r);        int maxw = -0x7fffffff;        for (int i = 1; i <= tot; ++i) {            maxw = max (maxw, tree[sta[i]].pre (w));        }        return maxw;    }        int nxt (int l, int r, int w) {        get_segment (l, r);        int minw = +0x7fffffff;        for (int i = 1; i <= tot; ++i) {            minw = min (minw, tree[sta[i]].nxt (w));        }        return minw;    }}tr;int read () {    int s = 0, ch = getchar ();    while (!isdigit (ch)) {        ch = getchar ();    }    while (isdigit (ch)) {        s = s * 10 + ch - '0';        ch = getchar ();    }    return s;}int main () {//  freopen ("data.in", "r", stdin);    srand (time (NULL));    n = read (), m = read ();    for (int i = 1; i <= n; ++i) {        int w = read ();        tr.modify (i, -1, w);        arr[i] = w;//      cout << endl;    }    int opt, pos, l, r, k;    for (int i = 1; i <= m; ++i) {        opt = read ();        if (opt == 1) {            l = read (), r = read (), k = read ();            cout << tr.rank (l, r, k) << endl;        }        if (opt == 2) {            l = read (), r = read (), k = read ();            cout << tr.kth (l, r, k) << endl;        }           if (opt == 3) {            pos = read (), k = read ();            tr.modify (pos, arr[pos], k);            arr[pos] = k;        }         if (opt == 4) {            l = read (), r = read (), k = read ();            cout << tr.pre (l, r, k) << endl;        }        if (opt == 5) {            l = read (), r = read (), k = read ();            cout << tr.nxt (l, r, k) << endl;        }    }}