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

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

洛谷 P3380. 【模板】二逼平衡树（树套树）原题链接中等

作者：

Fighting_Peter , 2020-08-24 14:10:25 , 所有人可见 , 阅读 802

【模板】二逼平衡树（树套树）
肖然大佬博客

题目描述

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

查询k在区间内的排名
查询区间内排名为k的值
修改某一位值上的数值
查询k在区间内的前驱(前驱定义为严格小于x，且最大的数，若不存在输出-2147483647)
查询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各输出一行，表示查询结果

数据范围

$n,m≤5⋅10^4$
保证有序序列所有值在任何时刻满足$[0,10^8]$

下标线段树套值域平衡树——时间$O(nlog^3n)$空间$O(nlogn)$

$log_2^{50000}\approx16$

$nlog^3n\approx2×10^8$

不开$O(2)$T3个点
首先，对于维护值域的平衡树通常可以采用权值线段树代替。

但是一般情况下，平衡树维护值域时，下标信息就会丢失，意味着不能维护类似下表是第 $i$ 个数是谁（除非开数组记录），因此也就不能维护区间 $[l,r]$ 内某个数的排名前驱后继等操作。

想要维护同时维护下标，必须外层用一个数据结构维护下标，比如可以采用（下标）线段树套（值域）平衡树。此时便可以支持同时维护【下标】和【值域】的操作。

查询 $k$ 在区间 $[l,r]$ 的排名：找到下标线段树上 $[l,r]$ 所对应的 $\log N$个终止结点，统计每个结点平衡树内 $<k$元素个数，求和 $+1$ 就是 $k$ 的排名，复杂度$O(n\log^2n)$。
查询区间 $[l,r]$ 内排名为 $k$ 的值：二分答案然后用Getrank判断，复杂度$O(n\log^3n)$。
修改某一位值上的数值 $a[i]=x$：只要在所有包含 $a[i]$ 的平衡树($\log N$个)中删除 $a[i]$，然后再插入 $x$ 即可，复杂度$O(n\log^2n)$。
查询 $x$ 在区间内$[l,r]$ 的前驱：在 $[l,r]$ 的所有终止结点的平衡树内查询前驱，取所有中止节点前驱的最大值，复杂度$O(n\log^2n)$。
查询 $x$ 在区间内 $[l,r]$ 的后继：在 $[l,r]$ 的所有终止结点的平衡树内查询后继，取所有中止节点后继的最小值，复杂度 $O(n\log^2n)$。

#include <random>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;
const int MINF = -2147483647, MAXF = 2147483647;
mt19937 rnd(233);
int n, m;
int a[N];
struct node {
    int l, r;
    int val, key;
    int sz;
} fhq[40 * N];
int cnt;
struct Treap {
    int l, r;
    int root;
    int newnode(int val) {
        fhq[++cnt].val = val;
        fhq[cnt].key = rnd();
        fhq[cnt].sz = 1;
        return cnt;
    }
    void pushup(int now) {
        fhq[now].sz = fhq[fhq[now].l].sz + fhq[fhq[now].r].sz + 1;
    }
    void split(int now, int val, int &x, int &y) {
        if (!now) {
            x = y = 0;
            return;
        }

        if (fhq[now].val <= val) {
            x = now;
            split(fhq[now].r, val, fhq[x].r, y);
        } else {
            y = now;
            split(fhq[now].l, val, x, fhq[y].l);
        }

        pushup(now);
    }
    int merge(int x, int y) {
        if (!x || !y)
            return x + y;

        if (fhq[x].key > fhq[y].key) {
            fhq[x].r = merge(fhq[x].r, y);
            pushup(x);
            return x;
        } else {
            fhq[y].l = merge(x, fhq[y].l);
            pushup(y);
            return y;
        }
    }
    void insert(int val) {
        int x, y;
        split(root, val, x, y);
        root = merge(merge(x, newnode(val)), y);
    }
    void del(int val) {
        int x, y, z;
        split(root, val, x, z);
        split(x, val - 1, x, y);
        y = merge(fhq[y].l, fhq[y].r);
        root = merge(merge(x, y), z);
    }
    int getrank(int val) {
        int x, y;
        split(root, val - 1, x, y);
        int res = fhq[x].sz + 1;
        root = merge(x, y);
        return res;
    }
    int getval(int k) {
        int now = root;

        while (now) {
            if (fhq[fhq[now].l].sz + 1 == k)
                break;
            else if (fhq[fhq[now].l].sz + 1 > k)
                now = fhq[now].l;
            else {
                k -= fhq[fhq[now].l].sz + 1;
                now = fhq[now].r;
            }
        }

        return fhq[now].val;
    }
    int pre(int val) {
        int x, y;
        split(root, val - 1, x, y);
        int now = x;

        while (fhq[now].r)
            now = fhq[now].r;

        root = merge(x, y);
        return now ? fhq[now].val : MINF;
    }
    int suc(int val) {
        int x, y;
        split(root, val, x, y);
        int now = y;

        while (fhq[now].l)
            now = fhq[now].l;

        root = merge(x, y);
        return now ? fhq[now].val : MAXF;
    }
} tree[N * 4];
void build(int u, int l, int r) {
    tree[u].l = l, tree[u].r = r;

    for (int i = l; i <= r; i++)
        tree[u].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 pos, int x) {
    tree[u].del(a[pos]);
    tree[u].insert(x);

    if (tree[u].l == tree[u].r)
        return;

    int mid = tree[u].l + tree[u].r >> 1;

    if (pos <= mid)
        modify(u << 1, pos, x);
    else
        modify(u << 1 | 1, pos, x);
}
int Grank(int u, int l, int r, int val) {
    if (l <= tree[u].l && tree[u].r <= r)
        return tree[u].getrank(val) - 1;

    int mid = tree[u].l + tree[u].r >> 1;
    int k = 0;

    if (l <= mid)
        k += Grank(u << 1, l, r, val);

    if (r > mid)
        k += Grank(u << 1 | 1, l, r, val);

    return k;
}
int Gval(int u, int l, int r, int k) {
    int vl = 0, vr = 1e8;

    while (vl < vr) {
        int mid = vl + vr + 1 >> 1;

        if (Grank(u, l, r, mid) + 1 <= k)
            vl = mid; //注意二分 需要二分排名<=k的最大数(数可能重复)
        else
            vr = mid - 1;
    }

    return vl;
}
int Gpre(int u, int l, int r, int val) {
    if (tree[u].l >= l && tree[u].r <= r)
        return tree[u].pre(val);

    int mid = tree[u].l + tree[u].r >> 1;

    if (r <= mid)
        return Gpre(u << 1, l, r, val);
    else if (l > mid)
        return Gpre(u << 1 | 1, l, r, val);
    else
        return max(Gpre(u << 1, l, r, val), Gpre(u << 1 | 1, l, r, val));
}
int Gsuc(int u, int l, int r, int val) {
    if (tree[u].l >= l && tree[u].r <= r)
        return tree[u].suc(val);

    int mid = tree[u].l + tree[u].r >> 1;

    if (r <= mid)
        return Gsuc(u << 1, l, r, val);
    else if (l > mid)
        return Gsuc(u << 1 | 1, l, r, val);
    else
        return min(Gsuc(u << 1, l, r, val), Gsuc(u << 1 | 1, l, r, val));
}
int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    build(1, 1, n);

    while (m--) {
        int op, l, r, k;
        cin >> op;

        if (op == 1) {
            cin >> l >> r >> k;
            cout << Grank(1, l, r, k) + 1 << endl;
        } else if (op == 2) {
            cin >> l >> r >> k;
            cout << Gval(1, l, r, k) << endl;
        } else if (op == 3) {
            cin >> l >> k;
            modify(1, l, k);
            a[l] = k;
        } else if (op == 4) {
            cin >> l >> r >> k;
            cout << Gpre(1, l, r, k) << endl;
        } else {
            cin >> l >> r >> k;
            cout << Gsuc(1, l, r, k) << endl;
        }
    }

    return 0;
}

值域线段树套下标平衡树——时间$O(nlog^2n)$空间$O(nlogn)$

动态开点值域线段树
不开$O(2)$T2个点(没准用scanf能过)
上述方法发现操作2是瓶颈，采用值域线段树后可以在树上进行二分

当然可以用动态开点线段树维护值域，也就是权值线段树，用平衡树维护下标

查询 $k$ 在区间 $[l,r]$ 的排名： 找到值域线段树上 $[0,k-1]$ 所对应的 $\log N$个终止结点，统计每个结点平衡树下标在 $[l,r]$ 区间内元素个数即求出区间为 $[l,r]$ 内值域在 $[0,k-1]$点的个数，求和+1就是 $k$ 的排名，复杂度 $O(n\log^2n)$。
查询区间 $[l,r]$ 内排名为 $k$ 的值：在值域线段树上二分，每次看值域范围 $[vl,mid]$ 中 $[L,R]$ 区间中数的个数 = tree[u].treap.query(L, R) 与 $k$ 的关系，$\ge k$ 递归左子树，否则递归右子树，复杂度 $O(n\log^2 n)$。
修改某一位值上的数值 $a[i]=x$：只要在所有包含 $a[i]$ 的平衡树($\log {|a[i]|}$个) 中删除 $a[i]$，然后再插入 $x$ 即可，复杂度 $O(n\log^2n)$。
查询 $x$ 在区间内$[l,r]$ 的前驱： 先用操作1查询 $x$ 在 $[l,r]$ 内的排名 $k$，然后再用操作2查询排名为$k-1$ 数，复杂度 $O(n\log^2n)$。
查询 $x$ 在区间内 $[l,r]$ 的后继：先用Query求出区间在 $[l,r]$ 内值域 $[0,x]$ 的个数 $k$，然后再用操作2查询排名为 $k+1$数，复杂度 $O(n\log^2n)$。

#pragma GCC optimize(2)
#include <random>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;
const int MINF = -2147483647, MAXF = 2147483647;
mt19937 rnd(233);
int n, m;
int a[N];
struct node {
    int l, r;
    int val, key;
    int sz;
} fhq[40 * N];
int cnt, idx;
int Root;
struct Treap {
    int l, r;
    int root;
    int newnode(int val) {
        fhq[++cnt].val = val;
        fhq[cnt].key = rnd();
        fhq[cnt].sz = 1;
        return cnt;
    }
    void pushup(int now) {
        fhq[now].sz = fhq[fhq[now].l].sz + fhq[fhq[now].r].sz + 1;
    }
    void split(int now, int val, int &x, int &y) {
        if (!now) {
            x = y = 0;
            return;
        }

        if (fhq[now].val <= val) {
            x = now;
            split(fhq[now].r, val, fhq[x].r, y);
        } else {
            y = now;
            split(fhq[now].l, val, x, fhq[y].l);
        }

        pushup(now);
    }
    int merge(int x, int y) {
        if (!x || !y)
            return x + y;

        if (fhq[x].key > fhq[y].key) {
            fhq[x].r = merge(fhq[x].r, y);
            pushup(x);
            return x;
        } else {
            fhq[y].l = merge(x, fhq[y].l);
            pushup(y);
            return y;
        }
    }
    int query(int L, int R) {
        int x, y, z;
        split(root, L - 1, x, z);
        split(z, R, y, z);
        int res = fhq[y].sz;
        root = merge(merge(x, y), z);
        return res;
    }
    void insert(int val) {
        int x, y;
        split(root, val, x, y);
        root = merge(merge(x, newnode(val)), y);
    }
    void del(int val) {
        int x, y, z;
        split(root, val, x, z);
        split(x, val - 1, x, y);
        y = merge(fhq[y].l, fhq[y].r);
        root = merge(merge(x, y), z);
    }
} tree[N * 40];
void Insert(int &u, int l, int r, int pos, int x) {
    if (!u)
        u = ++idx;

    tree[u].insert(x);

    if (l == r)
        return;

    int mid = l + r >> 1;

    if (pos <= mid)
        Insert(tree[u].l, l, mid, pos, x);
    else
        Insert(tree[u].r, mid + 1, r, pos, x);
}
void Del(int u, int l, int r, int pos, int x) {
    if (!u)
        return;

    tree[u].del(x);

    if (l == r)
        return;

    int mid = l + r >> 1;

    if (pos <= mid)
        Del(tree[u].l, l, mid, pos, x);
    else
        Del(tree[u].r, mid + 1, r, pos, x);
}
int Query(int u, int l, int r, int vl, int vr, int L,
          int R) { //实际上是求在区间[L,R]内值域在[vl,vr]点的个数
    if (!u)
        return 0;

    if (vl <= l && r <= vr)
        return tree[u].query(L, R);

    int mid = l + r >> 1;
    int v = 0;

    if (vl <= mid)
        v += Query(tree[u].l, l, mid, vl, vr, L, R);

    if (vr > mid)
        v += Query(tree[u].r, mid + 1, r, vl, vr, L, R);

    return v;
}
int Gval(int u, int l, int r, int L, int R, int k) {
    if (l == r)
        return l;

    int mid = l + r >> 1;
    int tmp = 0;

    if (tree[u].l)
        tmp = tree[tree[u].l].query(L, R);

    if (tmp >= k)
        return Gval(tree[u].l, l, mid, L, R, k);
    else
        return Gval(tree[u].r, mid + 1, r, L, R, k - tmp);
}
int main() {

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        Insert(Root, 0, 1e8, a[i], i);
    }

    while (m--) {
        int op, l, r, k;
        cin >> op;

        if (op == 1) {
            cin >> l >> r >> k;
            cout << Query(Root, 0, 1e8, 0, k - 1, l, r) + 1 << endl;
        } else if (op == 2) {
            cin >> l >> r >> k;
            cout << Gval(Root, 0, 1e8, l, r, k) << endl;
        } else if (op == 3) {
            cin >> l >> k;
            Del(Root, 0, 1e8, a[l], l);
            Insert(Root, 0, 1e8, k, l);
            a[l] = k;
        } else if (op == 4) {
            cin >> l >> r >> k;
            int x = Query(Root, 0, 1e8, 0, k - 1, l, r) + 1;

            if (x <= 1)
                cout << MINF << endl;
            else
                cout << Gval(Root, 0, 1e8, l, r, x - 1) << endl;
        } else {
            cin >> l >> r >> k;
            int x = Query(Root, 0, 1e8, 0, k, l, r);

            if (x == r - l + 1)
                cout << MAXF << endl;
            else
                cout << Gval(Root, 0, 1e8, l, r, x + 1) << endl;
        }
    }

    return 0;
}

永远不想再写树套树了，debug都是一个一个操作搞，快哭了www