欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P3380 【模板】二逼平衡树(树套树)

程序员文章站 2022-06-20 14:44:59
题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作: 查询k在区间内的排名 查询区间内排名为k的值 修改某一位值上的数值 查询k在区间内的前驱(前驱定义为严格小于x,且最大的数,若不存在输出-2147483647) 查询k在区间内的后继(后继定义为严格大于x, ......

题目描述

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

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

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

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

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

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

注意上面两条要求和tyvj或者bzoj不一样,请注意

输入输出格式

输入格式:

 

第一行两个数 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

说明

时空限制:2s,128M

n,m \leq 5\cdot {10}^4n,m5104 保证有序序列所有值在任何时刻满足 [0, {10} ^8][0,108]

题目来源:bzoj3196 / Tyvj1730 二逼平衡树,在此鸣谢

此数据为洛谷原创。(特别提醒:此数据不保证操作5、6一定存在,故请务必考虑不存在的情况)

 

复习了一下树套树

感觉很套路啊qwq,

然而不想重写, 所以就对着以前的抄了一遍。

 

// luogu-judger-enable-o2
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;
const int MAXN = 2000001;
inline int read() {
    char c = getchar();int x = 0,f = 1;
    while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}
    return x * f;
}
#define Ls(k) s[k].ch[0]
#define Rs(k) s[k].ch[1]
struct sp {
    int siz, ch[2], fa, rev, num;
} s[MAXN];
int sz;
inline void pushup(int k) { //上传splay标记
    s[k].siz = s[s[k].ch[0]].siz + s[s[k].ch[1]].siz + s[k].rev;
}
inline int ident(int x) { // 判断x是父亲的哪个儿子
    return s[s[x].fa].ch[1] == x;
}
inline void connect(int x, int f, int how) {
    s[x].fa = f; s[f].ch[how] = x;
}
inline void rotate(int &root,int x) { // 对x进行双旋操作
    int Y = s[x].fa, R = s[Y].fa, Yson = ident(x), Rson = ident(Y);
    int B = s[x].ch[Yson ^ 1];
    if(!R) root = x;
    connect(x, R, Rson);
    connect(Y, x, Yson ^ 1);
    connect(B, Y, Yson);
    pushup(Y); pushup(x);
}
inline void splay(int &root, int x, int to) { // tag
    while(s[x].fa != to) {
        int y = s[x].fa;
        if(s[y].fa == to) rotate(root, x);
        else if(ident(x) == ident(y)) rotate(root, y),rotate(root, x);
        else rotate(root, x),rotate(root, x);
    }
}
inline void insert(int &k, int c) { // k节点,插入值为c的元素
    if(k == 0) { 
        k=++sz;
        s[k].siz = s[k].rev = 1; s[k].num = c;
        return ;
    }
    if(s[k].num==c) s[k].rev++;
    else if(s[k].num < c) insert(Rs(k), c), s[Rs(k)].fa = k;
    else insert(Ls(k), c), s[Ls(k)].fa = k;
    pushup(k);
}
inline int getpre(int k,int val) { //小于val的最大值
    int pos = k, ret;
    while(pos) {
        if(s[pos].num >= val) pos = Ls(pos);
        else ret = pos, pos = Rs(pos);
    }
    return ret;
}
inline int getsuc(int k,int val) {
    int pos = k, ret;
    while(pos) {
        if(s[pos].num <= val) pos = s[pos].ch[1];
        else ret = pos, pos = s[pos].ch[0];
    }
    return ret;
}
inline int getk(int k,int val) {
    if(s[k].num == val)   return k;
    if(s[k].num < val)    return getk(Rs(k),val);
    if(s[k].num > val)    return getk(Ls(k),val);
}


#define ls k << 1
#define rs k << 1 | 1
struct node {
    int l, r, root, mx, mn;
} T[MAXN];
inline void pushup_s(int k) { // 上传线段树的标记
    T[k].mx = max(T[ls].mx, T[rs].mx);
    T[k].mn = min(T[ls].mn, T[rs].mn);
}
inline void Build(int k,int l,int r) { //下标为k,左端点为l,右端点为r
    T[k].l = l; T[k].r = r;
    if(l == r)    return ;
    int mid = (l + r) >> 1;
    Build(ls, l, mid);
    Build(rs, mid + 1, r);// 线段树模板,没啥好说的,
}
inline void delet(int &k, int val) { //删除值为val的节点
    int x = getk(k,val);//得到值为val的编号
    if(s[x].rev > 1) { 
        s[x].rev--; s[x].siz--;
        splay(k, x, 0);
    } else {
        int p = getpre(k, val),su = getsuc(k, val);// 找到前驱和后继
        splay(k, p, 0); splay(k, su, p);// 把前驱旋转到根节点,把后继旋转到根节点的孩子 
        Ls(su) = 0;// 删除后继的左孩子,表示没有小于他的点,这样就成功把x节点删除 
    }
}
inline void build(int k, int pos, int x) { // 在下标为k,位置为pos的地方插入一个值为x的元素 
    insert(T[k].root, x);//在线段树root节点的splay中插入一个值为x的元素
    if(T[k].l == T[k].r) {
        T[k].mx = x; T[k].mn = x; 
        return ;
    }
    int mid = (T[k].l + T[k].r) >> 1;
    if(pos <= mid)    build(ls, pos, x);
    if(pos > mid)    build(rs, pos, x);
    pushup_s(k);//别忘了上传线段树标记 
}
int NewNode(int val, int f) {
    s[++sz].rev = s[sz].siz = 1;
    s[sz].num = val; s[sz].fa = f;
    return sz;
}
inline void dfsseg(int k) { //对以k下标开始的线段树进行遍历
    int x = getsuc(T[k].root, -1),
        y = getpre(T[k].root, 1e8+1);//这样计算出来的x和y一定满足:x是k号线段树中的最小值的位置,y是k号线段树中最大值的位置
    splay(T[k].root, x, 0);//将x旋转到根
    s[x].siz++;
    s[x].ch[0] = NewNode(-1, x);
    splay(T[k].root, y, 0);
    s[y].siz++;
    s[y].ch[1] = NewNode(1e8 + 1, y);
    if(T[k].l == T[k].r)    return ;
    dfsseg(ls);
    dfsseg(rs);// 对于每一个线段,增加两个虚节点
}
inline int getmax(int k,int l,int r) { //在l到r中找最大的元素
    if(l <= T[k].l && T[k].r <= r) return T[k].mx;
    int mid=(T[k].l + T[k].r) >> 1,ret = -1;
    if(l <= mid)    ret = max(ret, getmax(ls, l, r));
    if(mid <  r)    ret = max(ret, getmax(rs, l, r));
    return ret;
}
inline int getmin(int k,int l,int r) { //在l到r中找最小的元素
    if(l <= T[k].l && T[k].r <= r) return T[k].mn;
    int mid = (T[k].l + T[k].r) >> 1,ret = 1e8+1;
    if(l <= mid)    ret = min(ret, getmin(ls, l, r));
    if(mid <  r)    ret = min(ret, getmin(rs, l, r));
    return ret;
}
inline int query_order(int k, int l, int r, int val) { //下标为k,查询val在区间l到r中有多少比它小的数
    if(l <= T[k].l && T[k].r <= r) {
        int p = getpre(T[k].root, val);
        splay(T[k].root, p, 0);
        return s[p].siz - s[Rs(p)].siz - 1;//
    } 
    int mid = (T[k].l + T[k].r) >> 1, ret = 0;
    if(l <= mid)    ret += query_order(ls, l, r, val);
    if(r >  mid)    ret += query_order(rs, l, r, val);
    return ret;
}

inline void modify(int k,int pos,int pre,int now) { //在下标为k的线段树中的pos位置值为pre的节点的值修改为now
    delet(T[k].root, pre);// 先把pre删掉
    insert(T[k].root, now);// 再把now加上
    if(T[k].l==T[k].r) {
        T[k].mx = now; T[k].mn = now; 
        return ;
    }
    int mid = (T[k].l + T[k].r) >> 1;
    if(pos <= mid)    modify(ls , pos, pre, now);
    if(pos >  mid)    modify(rs , pos, pre, now);
    pushup_s(k);// 别忘了上传标记!
}
inline int query_pre(int k,int l,int r,int val) {//查询区间l到r内val的前驱 
    if(l <= T[k].l && T[k].r <= r) return s[getpre(T[k].root,val)].num;
    int mid = (T[k].l + T[k].r) >> 1,ret = -1;
    if(l <= mid)    ret = max(ret, query_pre(ls, l, r, val));
    if(mid < r)        ret = max(ret, query_pre(rs, l, r, val));
    return ret;
}
inline int query_suc(int k,int l,int r,int val) {//查询区间l到r内val的后继 
    if(l <= T[k].l && T[k].r <= r) return s[getsuc(T[k].root,val)].num;
    int mid = (T[k].l + T[k].r) >> 1, ret = 1e8 + 1;
    if(l <= mid)    ret = min(ret, query_suc(ls, l, r, val));
    if(mid <  r)    ret = min(ret, query_suc(rs, l, r, val));
    return ret;
}
inline int QueryNum(int L,int R,int val) { // 在L到R的区间中查找val的排名
    int l = 1, r = getmax(1, L, R), ret, tmp;
    while(l <= r) { //二分答案
        int mid = (l + r) >> 1;
        tmp = query_order(1, L, R, mid);
        if(tmp < val) ret = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ret;
}
int n, m;
int date[MAXN];
int main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    n = read(); m = read();
    Build(1, 1, n);//建好线段树
    for(int i = 1; i <= n; i++) date[i] = read(); //读入初始数据
    for(int i = 1; i <= n; i++)
        build(1, i, date[i]);//把每一个元素都插到线段树里面去
    dfsseg(1);// 把线段树的所有节点增加两个虚节点
    while(m--) {
        int l, r, k, pos, opt;
        opt = read();
        if(opt == 1) { //查询k在l到r中的排名
            l = read(); r = read(); k = read();
            printf("%d\n",query_order(1, l, r, k) + 1);
        }
        if(opt == 2) { // 查询排名为k的值
            l = read(); r = read(); k = read();
            printf("%d\n", QueryNum(l, r, k));
        }
        if(opt==3) { // 将pos位置的数修改为k
            pos = read(); k = read();
            modify(1, pos, date[pos], k);
            date[pos] = k;//顺便修改date的值
        }
        if(opt==4) {
            l = read(); r = read(); k = read();
            int tmp = query_pre(1, l, r, k);// 查询tmp的前驱
            if(tmp != -1) printf("%d\n", tmp);
            else printf("-2147483647\n");
        }
        if(opt == 5) {
            l = read(); r = read(); k = read();
            int tmp = query_suc(1,l,r,k);
            if(tmp != 1e8 + 1) printf("%d\n", tmp);
            else printf("2147483647\n");
        }
    }
    return 0;
}