P3380 【模板】二逼平衡树（树套树）

样例没过，还有注释保留

#include <bits/stdc++.h>
using namespace std;
const int Size = 1e5 + 10, INF = INT_MAX;
int in[Size], n, q;
namespace Treap
{
int root = 0, tot = 0, n, inf = 0x7fffffff;
struct treap
{
    int l, r;      // 左右儿子的下标
    int val, dat;  // 节点关键码、权值
    int cnt, siz;  // 副本数、字数大小
} a[Size * 40];
int New(int val)
{
    a[++tot].val = val;
    a[tot].dat = rand();
    a[tot].cnt = a[tot].siz = 1;
    a[tot].l = a[tot].r = 0;
    return tot;
}
void push_up(int p) { a[p].siz = a[a[p].l].siz + a[a[p].r].siz + a[p].cnt; }
void Build()
{
    New(-inf), New(inf);
    root = 1;
    a[1].r = 2;
    push_up(root);
}
int GetRankByVal(int p, int val)
{
    if (p == 0)
        return 0;
    if (val == a[p].val)
        return a[a[p].l].siz;
    if (val < a[p].val)
        return GetRankByVal(a[p].l, val);
    return GetRankByVal(a[p].r, val) + a[a[p].l].siz + a[p].cnt;
}
// int GetValByRank(int p, int rank)
// {
//     if (p == 0)
//         return inf;
//     if (a[a[p].l].siz >= rank)
//         return GetValByRank(a[p].l, rank);
//     if (a[a[p].l].siz + a[p].cnt >= rank)
//         return a[p].val;
//     return GetValByRank(a[p].r, rank - a[a[p].l].siz - a[p].cnt);
// }
void zig(int &p)
{  // 左旋
    int q = a[p].l;
    a[p].l = a[q].r;
    a[q].r = p;
    push_up(p);
    push_up(q);
    p = q;
}
void zag(int &p)
{  // 右旋
    int q = a[p].r;
    a[p].r = a[q].l;
    a[q].l = p;
    push_up(p);
    push_up(q);
    p = q;
}
void Insert(int &p, int val)
{  // 插入
    if (!p)
    {
        p = New(val);
    }
    else if (val == a[p].val)
    {
        a[p].cnt++;
    }
    else
    {
        if (val < a[p].val)
        {
            Insert(a[p].l, val);
            if (a[p].dat < a[a[p].l].dat)
                zig(p);
        }
        else
        {
            Insert(a[p].r, val);
            if (a[p].dat < a[a[p].r].dat)
                zag(p);
        }
    }
    push_up(p);
}
void Remove(int &p, int val)
{  // 删除 p
    if (a[p].val > val)
        Remove(a[p].l, val);
    else if (a[p].val < val)
        Remove(a[p].r, val);
    else
    {
        if (a[p].cnt > 1)
        {
            a[p].cnt--;
        }
        else
        {
            if (!a[p].l && !a[p].r)
                p = 0;
            else if (!a[p].l)
            {
                zag(p);
                Remove(a[p].l, val);
            }
            else if (!a[p].r)
            {
                zig(p);
                Remove(a[p].r, val);
            }
            else
            {
                if (a[a[p].l].dat > a[a[p].r].dat)
                {
                    zig(p);
                    Remove(a[p].r, val);
                }
                else
                {
                    zag(p);
                    Remove(a[p].l, val);
                }
            }
        }
    }
    if (p)
        push_up(p);
}
int GetPre(int p, int val)
{  // 前驱
    int ans = 1;
    while (p)
    {
        if (val == a[p].val)
        {
            if (a[p].l > 0)
            {
                p = a[p].l;
                while (a[p].r > 0) p = a[p].r;
                ans = p;
            }
            break;
        }
        if (a[p].val < val && a[p].val > a[ans].val)
            ans = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return a[ans].val;
}
int GetNext(int p, int val)
{  // 后继
    int ans = 2;
    while (p)
    {
        if (val == a[p].val)
        {
            if (a[p].r > 0)
            {
                p = a[p].r;
                while (a[p].l > 0) p = a[p].l;
                ans = p;
            }
            break;
        }
        if (a[p].val > val && a[p].val < a[ans].val)
            ans = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return a[ans].val;
}
}  // namespace Treap
namespace Segment
{
struct segment
{
    int l, r, root;
} tr[Size * 40];
void build(int p, int l, int r)
{  // 建树
    tr[p].l = l;
    tr[p].r = r;
    for (int i = l; i < r + 1; i++)
    {
        Treap::Insert(tr[p].root, in[i]);
    }
    if (l != r)
    {
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
    }
}
void update(int p, int x, int y)
{  // 插入
    printf("update = %d\n", p);
    Treap::Remove(tr[p].root, in[x]);
    Treap::Insert(tr[p].root, y);
    if (tr[p].l == tr[p].r)
    {
        return;
    }
    int mid = (tr[p].l + tr[p].r) / 2;
    if (mid <= x)
        update(p << 1, x, y);
    else
        update(p << 1 | 1, x, y);
}
int QueryRankByNumber(int p, int l, int r, int k)
{
    if (tr[p].l > r || tr[p].r < l)
        return 0;
    if (tr[p].l >= l && tr[p].r <= r)
        return Treap::GetRankByVal(tr[p].root, k);
    return QueryRankByNumber(p << 1, l, r, k) +
           QueryRankByNumber(p << 1 | 1, l, r, k);
}
int QueryNumberByRank(int l, int r, int k)
{
    int pl = 0, pr = 1e8;
    while (pl < pr)
    {
        int mid = (pl + pr + 1) / 2;
        if (QueryRankByNumber(1, l, r, mid) < k)
            pl = mid;
        else
            pr = mid - 1;
    }
    return pr;
}
int prenum(int p, int l, int r, int k)
{
    if (tr[p].l > r || tr[p].r < l)
        return -INF;
    if (tr[p].l >= l && tr[p].r >= r)
        return Treap::GetPre(tr[p].root, k);
    int mid = (l + r) >> 1;
    return max(prenum(p << 1, l, mid, k), prenum(p << 1, mid + 1, r, k));
}
int nxtnum(int p, int l, int r, int k)
{
    if (tr[p].l > r || tr[p].r < l)
        return INF;
    if (tr[p].l >= l && tr[p].r >= r)
        return Treap::GetNext(tr[p].root, k);
    int mid = (l + r) >> 1;
    return max(nxtnum(p << 1, l, mid, k), nxtnum(p << 1, mid + 1, r, k));
}
}  // namespace Segment
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &in[i]);
    Segment::build(1, 1, n);
    while (q--)
    {
        int opt, l, r, k;
        scanf("%d%d%d", &opt, &l, &r);
        switch (opt)
        {
        case 1:
            scanf("%d", &k);
            printf("%d\n", Segment::QueryRankByNumber(1, l, r, k) + 1);
            break;
        case 2:
            scanf("%d", &k);
            printf("%d\n", Segment::QueryNumberByRank(l, r, k));
            break;
        case 3:
            Segment::update(1, l, r);
            in[l] = r;
            break;
        case 4:
            scanf("%d", &k);
            printf("%d\n", Segment::prenum(1, l, r, k));
            break;
        default:
            scanf("%d", &k);
            printf("%d\n", Segment::nxtnum(1, l, r, k));
            break;
        }
    }
}