第一次写树套树，在一定帮助下学习，调码3h。

用线段树套平衡树，

对于区间内排名的查询可以解决了；//$O(log^2n)$

对于查询区间排名为k的数，二分答案再判断；//$O(log^3n)$

修改数值直接修改；// $O(log^2n)$

前驱后继，线段树递归区间时，查询每个完全包括的区间数v的前驱后继，最后取min/max即可。// $O(log^2n)$

1 #include 
     
        2   3 using namespace std;  4   5 #define re register  6 #define rep(i, a, b) for (re int i = a; i <= b; ++i)  7 #define repd(i, a, b) for (re int i = a; i >= b; --i)  8 #define maxx(a, b) a = max(a, b);  9 #define minn(a, b) a = min(a, b); 10 #define LL long long 11 #define INF (1 << 30) 12  13 inline int read() { 14     int w = 0, f = 1; char c = getchar(); 15     while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar(); 16     while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar(); 17     return w * f; 18 } 19  20 const int maxn = 5e4 + 5; 21  22 struct Node { 23     Node* ch[2]; 24     int v, s, r; 25     Node(int v, Node *son) : v(v) { s = 1; r = rand(); ch[0] = ch[1] = son; } 26     void maintain() { s = ch[0]->s + ch[1]->s + 1; } 27 } *null; 28  29 void initnull() { null = new Node(0, NULL); null->ch[0] = null->ch[1] = null; null->s = 0; } 30  31 Node* merge(Node *a, Node *b) { 32     if (a == null) return b; 33     if (b == null) return a; 34     if (a->r > b->r) { a->ch[1] = merge(a->ch[1], b); a->maintain(); return a; } 35     b->ch[0] = merge(a, b->ch[0]); b->maintain(); return b; 36 } 37  38 void split_val(Node *o, int v, Node* &l, Node* &r) { 39     if (o == null) { l = r = null; return; } 40     if (o->v <= v) { l = o; split_val(o->ch[1], v, l->ch[1], r); } 41     else { r = o; split_val(o->ch[0], v, l, r->ch[0]); } 42     o->maintain(); 43 } 44  45 void split_rank(Node *o, int k, Node* &l, Node* &r) { // 这个过程好像没用 46     if (o == null) { l = r = null; return; } 47     if (o->ch[0]->s + 1 <= k) { l = o; split_rank(o->ch[1], k - o->ch[0]->s - 1, l->ch[1], r); } 48     else { r = o; split_rank(o->ch[0], k, l, r->ch[0]); } 49     o->maintain(); 50 } 51  52 void insert(Node* &root, int v) { 53     Node *l, *r; 54     split_val(root, v, l, r); 55     root = merge(merge(l, new Node(v, null)), r); 56 } 57  58 void remove(Node* &root, int v) { 59     Node *l, *mid, *r; 60     split_val(root, v-1, l, r); 61     split_val(r, v, mid, r); 62     root = merge(merge(l, merge(mid->ch[0], mid->ch[1])), r); 63     delete mid; 64 } 65  66 int get_rank(Node *o, int v) { 67     if (o == null) return 0; 68     if (o->v < v) return get_rank(o->ch[1], v) + o->ch[0]->s + 1; 69     return get_rank(o->ch[0], v); 70 } 71  72 int get_val(Node *o, int k) { 73     if (o == null) return -INF; 74     if (k <= o->ch[0]->s) return get_val(o->ch[0], k); 75     if (k > o->ch[0]->s + 1) return get_val(o->ch[1], k - o->ch[0]->s - 1); 76     return o->v; 77 } 78  79 #define ERROR 2147483647 80  81 int get_pre(Node *o, int v) { 82     if (o == null) return -ERROR; 83     if (o->v >= v) return get_pre(o->ch[0], v); 84     return max(o->v, get_pre(o->ch[1], v)); 85 } 86  87 int get_next(Node *o, int v) { 88     if (o == null) return ERROR; 89     if (o->v <= v) return get_next(o->ch[1], v); 90     return min(o->v, get_next(o->ch[0], v)); 91 } 92  93 int a[maxn], n, m; 94  95 void out(Node *o) { 96     if (o == null) return; 97     out(o->ch[0]); 98     printf("%d ", o->v); 99     out(o->ch[1]);100 }101 102 struct Seg_tree {103 #define lson (o << 1)104 #define rson (o << 1 | 1)105     Node *root[maxn << 4];106     void build(int o, int l, int r) {107         root[o] = null;108         rep(i, l, r)109             insert(root[o], a[i]);110         if (l == r) return;111         int mid = (l + r) >> 1;112         build(lson, l, mid), build(rson, mid+1, r);113         //out(root[o]); puts("\n");114     }115     void modify(int o, int l, int r, int p, int ov, int nv) {116         //reset(root[o], p, v);117         remove(root[o], ov);118         insert(root[o], nv);119         if (l == r) return;120         int mid = (l + r) >> 1;121         if (p <= mid) modify(lson, l, mid, p, ov, nv);122         else modify(rson, mid+1, r, p, ov, nv);123     }124     int query_rank(int o, int l, int r, int ql, int qr, int v) {125         if (r < ql || qr < l) return 0;126         if (ql <= l && r <= qr) return get_rank(root[o], v);127         int mid = (l + r) >> 1;128         return query_rank(lson, l, mid, ql, qr, v) + query_rank(rson, mid+1, r, ql, qr, v);129     }130     int query_val(int ql, int qr, int k) {131         int l = 0, r = 1e8;132         while (l < r) {133             int mid = (l + r + 1) >> 1, cmp = query_rank(1, 1, n, ql, qr, mid);134             if (cmp >= k) r = mid-1;135             else if (cmp < k) l = mid;136         }137         return l;138     }139     int query_pre(int o, int l, int r, int ql, int qr, int v) {140         if (r < ql || qr < l) return -ERROR; 141         if (ql <= l && r <= qr) return get_pre(root[o], v);142         int mid = (l + r) >> 1;143         return max(query_pre(lson, l, mid, ql, qr, v), query_pre(rson, mid+1, r, ql, qr, v));144     }145     int query_next(int o, int l, int r, int ql, int qr, int v) {146         if (r < ql || qr < l) return ERROR;147         if (ql <= l && r <= qr) return get_next(root[o], v);148         int mid = (l + r) >> 1;149         return min(query_next(lson, l, mid, ql, qr, v), query_next(rson, mid+1, r, ql, qr, v));150     }151 } seg_root;152 153 #undef ERROR154 155 int main() {156     srand(19260817);157     initnull();158     n = read(), m = read();159     rep(i, 1, n) a[i] = read();160     seg_root.build(1, 1, n);161     while (m--) {162         int opt = read();163         if (opt == 3) {164             int pos = read(), k = read();165             seg_root.modify(1, 1, n, pos, a[pos], k);166             a[pos] = k;167         }168         else {169             int l = read(), r = read(), k = read();170             if (opt == 1) printf("%d\n", seg_root.query_rank(1, 1, n, l, r, k)+1);171             if (opt == 2) printf("%d\n", seg_root.query_val(l, r, k));172             if (opt == 4) printf("%d\n", seg_root.query_pre(1, 1, n, l, r, k));173             if (opt == 5) printf("%d\n", seg_root.query_next(1, 1, n, l, r, k));174         }175     }176     return 0;177 }