树套树-简单版

解题思路

本题要求我们实现两个操作，一个是单点修改，一个是查询某个区间内某一个数的前驱。

单点修改不用说，比较好实现，对于查询某一个区间内的某一个数的前驱，如果我们将区间限制去掉，这就是一个非常简单的找前驱问题，直接用平衡树或者 set 来求，这里由于只有一个找前驱的操作，为了方便直接用 set 即可，我们要找的前驱就是 $< x$ 的最大的数，而 lower_bound 可以找出 $>= x$ 的最小的数，而这个数的前一个数就是 $< x$ 的最大的数。

至于单点修改，对于 set 来说也很好实现，我们只需要找到 $x$，把它删掉并插入一个新的值，就能实现单点修改。

现在再加上这个区间的限制，我们知道，要想将整个序列分成大大小小的若干个区间，每次对某一个区间内的数进行操作，这是线段树的经典操作，因此我们可以在外面套一层线段树来满足区间限制，对于线段树的每一个节点，也就是每一段区间，都用一个 set 去进行维护，这样就能用一个树套树的数据结构实现单点修改和区间找前驱的操作。

这里还有一个细节，我们用线段树去维护整个区间后，每次如果我们想找出某一段区间中 $x$ 的前驱，此时这个区间会由线段树中的某几段小区间拼凑而成，此时如果我们先知道这几段小区间拼凑而成的大区间中 $< x$ 的最大的数是多少，我们可以分别在每个小区间中求一下 $< x$ 的最大的数是多少，对于这些区间找出的数取一个最大值，就是整个区间中 $< x$ 的最大的数了，这样就实现了区间找前驱的操作。至于单点修改操作，我们只需要在线段树中从根节点开始，找出所有包含这个点的区间节点，对于每个区间中，我们将这个点删去，再加入一个新的值，就能实现单点修改。

注意，本题中没有规定区间中的数一定不相同，因此可能存在重复元素，所以不能用 set 来维护，需要用 multiset 来维护，multiset 可以存储重复元素。

C++ 代码

#include <iostream>
#include <cstring>
#include <set>

using namespace std;

const int N = 50010, INF = 0x3f3f3f3f;

struct Node
{
    int l, r;
    multiset<int> s; //平衡树
}tr[N * 4]; //线段树

int n, m;
int a[N]; //原序列

void build(int u, int l, int r) //初始化线段树
{
    tr[u] = {l, r};
    tr[u].s.insert(-INF), tr[u].s.insert(INF);
    for(int i = l; i <= r; i++) tr[u].s.insert(a[i]);
    if(l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int p, int x) //单点修改
{
    //修改所有包含 a[p] 的区间
    tr[u].s.erase(tr[u].s.find(a[p]));
    tr[u].s.insert(x);
    if(tr[u].l == tr[u].r) return;

    int mid = tr[u].l + tr[u].r >> 1;
    if(p <= mid) modify(u << 1, p, x);
    else modify(u << 1 | 1, p, x);
} 

int query(int u, int l, int r, int x) //区间查询前驱
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        //要查询 < x 的最大的数
        auto it = tr[u].s.lower_bound(x); //查询出 >= x 的最小的数
        --it; //>= x 的最小的数的前一位就是 < x 的最大的数
        return *it;
    }

    int mid = tr[u].l + tr[u].r >> 1;
    int res = -INF;
    if(l <= mid) res = max(res, query(u << 1, l, r, x));
    if(r > mid) res = max(res, query(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 pos, x;
            scanf("%d%d", &pos, &x);
            modify(1, pos, x);
            a[pos] = x;
        }
        else //区间查询前驱
        {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query(1, l, r, x));
        }
    }

    return 0;
}