树套树

例题：树套树

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

1. 查询 $k$ 在区间内的排名

2. 查询区间内排名为 $k$ 的值

3. 修改某一位值上的数值

4. 查询 $k$ 在区间内的前驱（前驱定义为严格小于 $x$，且最大的数，若不存在输出 -2147483647）

5. 查询 $k$ 在区间内的后继（后继定义为严格大于 $x$，且最小的数，若不存在输出 2147483647）

输入格式

第一行两个数 $n,m$，表示长度为 $n$ 的有序序列和 $m$ 个操作。

第二行有 $n$ 个数，表示有序序列。

下面有 $m$ 行，$opt$ 表示操作标号。

若 $opt=1$，则为操作 $1$，之后有三个数 $l、r、k$，表示查询 $k$ 在区间 $[l,r]$ 的排名。

若 $opt=2$，则为操作 $2$，之后有三个数 $l、r、k$，表示查询区间 $[l,r]$ 内排名为 $k$ 的数。

若 $opt=3$，则为操作 $3$，之后有两个数 $pos、k$，表示将 $pos$ 位置的数修改为 $k$。

若 $opt=4$，则为操作 $4$，之后有三个数 $l、r、k$，表示查询区间 $[l,r]$ 内 $k$ 的前驱。

若 $opt=5$，则为操作 $5$，之后有三个数 $l、r、k$，表示查询区间 $[l,r]$ 内 $k$ 的后继。

输出格式

对于操作 $1,2,4,5$，各输出一行，表示查询结果。

样例输入 #1

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

样例输出 #1

2
4
3
4
9

提示

$1\le n,m\le5\times 10^4$，序列中的值在任何时刻 $\in[0,10^8]$。
（特别提醒：此数据不保证操作 4、5 一定存在，故请务必考虑不存在的情况。）

---

一、思路

可使用线段树套平衡树来实现，即线段树的每个结点内都是一棵平衡树

这里使用线段树套$Splay$树

---

二、完整代码

时间复杂度：$O(Mlog^3N)$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 50010, M = 38 * N, INF = 2e9;

struct node {
    int s[2], p;
    int val;
    int size;
    void init(int _val, int _p) { s[0] = s[1] = 0, p = _p, val = _val, size = 1; }
} tr[M];

int idx;

int L[N << 2], R[N << 2], ROOT[N << 2];

int n, m;
int a[N];

void pushup(int u)
{
    tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
}

void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    
    pushup(y), pushup(x);
}

void splay(int &root, int x, int k)
{
    while(tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if(z != k)
        {
            if((tr[z].s[1] == y) == (tr[y].s[1] == x)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if(!k) root = x;
}

void insert(int &root, int val)
{
    int u = root, p = 0;
    while(u) p = u, u = tr[u].s[val > tr[u].val];
    u = ++ idx;
    if(p) tr[p].s[val > tr[p].val] = u;
    tr[u].init(val, p);
    splay(root, u, 0);
}

void build(int u, int l, int r)
{
    L[u] = l, R[u] = r;
    insert(ROOT[u], -INF), insert(ROOT[u], INF);
    for(int i = l; i <= r; i ++) insert(ROOT[u], a[i]);
    if(l >= r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void update(int &root, int y, int x)
{
    int u = root;
    while(u)
    {
        if(tr[u].val == y) break;
        else if(tr[u].val < y) u = tr[u].s[1];
        else u = tr[u].s[0];
    }
    splay(root, u, 0);
    int l = tr[u].s[0], r = tr[u].s[1];
    while(tr[l].s[1]) l = tr[l].s[1];
    while(tr[r].s[0]) r = tr[r].s[0];
    splay(root, l, 0), splay(root, r, l);
    tr[r].s[0] = 0;
    pushup(r), pushup(l);
    insert(root, x);
}

void modify(int u, int pos, int x)
{
    update(ROOT[u], a[pos], x);
    if(L[u] >= R[u]) return;
    int mid = L[u] + R[u] >> 1;
    if(pos <= mid) modify(u << 1, pos, x);
    else modify(u << 1 | 1, pos, x);
}

int get_cnt(int u, int x)
{
    int cnt = 0;
    while(u)
    {
        if(tr[u].val < x) cnt += tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
        else u = tr[u].s[0];
    }
    return cnt;
}

int get_pre(int u, int x)
{
    int res = -INF;
    while(u)
    {
        if(tr[u].val < x) res = max(res, tr[u].val), u = tr[u].s[1];
        else u = tr[u].s[0];
    }
    return res;
}

int get_suc(int u, int x)
{
    int res = INF;
    while(u)
    {
        if(tr[u].val > x) res = min(res, tr[u].val), u = tr[u].s[0];
        else u = tr[u].s[1];
    }
    return res;
}

int query_cnt(int u, int l, int r, int x)
{
    if(L[u] >= l && R[u] <= r) return get_cnt(ROOT[u], x) - 1;
    int mid = L[u] + R[u] >> 1;
    int cnt = 0;
    if(l <= mid) cnt += query_cnt(u << 1, l, r, x);
    if(r > mid) cnt += query_cnt(u << 1 | 1, l, r, x);
    return cnt;
}

int query_pre(int u, int l, int r, int x)
{
    if(L[u] >= l && R[u] <= r) return get_pre(ROOT[u], x);
    int mid = L[u] + R[u] >> 1;
    int res = -INF;
    if(l <= mid) res = max(res, query_pre(u << 1, l, r, x));
    if(r > mid) res = max(res, query_pre(u << 1 | 1, l, r, x));
    return res;
}

int query_suc(int u, int l, int r, int x)
{
    if(L[u] >= l && R[u] <= r) return get_suc(ROOT[u], x);
    int mid = L[u] + R[u] >> 1;
    int res = INF;
    if(l <= mid) res = min(res, query_suc(u << 1, l, r, x));
    if(r > mid) res = min(res, query_suc(u << 1 | 1, l, r, x));
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    build(1, 1, n);
    while(m --)
    {
        int op;
        scanf("%d", &op);
        if(op == 1)
        {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query_cnt(1, l, r, x) + 1);
            
        }
        else if(op == 2)
        {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            int left = 0, right = 1e8;
            while(left < right)
            {
                int mid = left + right + 1 >> 1;
                if(query_cnt(1, l, r, mid) >= k) right = mid - 1;
                else left = mid;
            }
            printf("%d\n", right);
        }
        else if(op == 3)
        {
            int pos, x;
            scanf("%d%d", &pos, &x);
            modify(1, pos, x);
            a[pos] = x;
        }
        else if(op == 4)
        {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            int res = query_pre(1, l, r, x);
            if(res == -INF) puts("-2147483647");
            else printf("%d\n", res);
        }
        else if(op == 5)
        {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            int res = query_suc(1, l, r, x);
            if(res == INF) puts("2147483647");
            else printf("%d\n", res);
        }
    }
    return 0;
}