2018年4月5日

[洛谷3380]【模板】二逼平衡树（树套树） 题解

[洛谷3380]【模板】二逼平衡树（树套树） 题解

题目地址：洛谷：【P3380】【模板】二逼平衡树（树套树） – 洛谷、BZOJ：Problem 3196. — Tyvj 1730 二逼平衡树

题目描述

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

  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

说明

时空限制：2s，128M
n,m≤5*10^4保证有序序列所有值在任何时刻满足[0,10^8]
题目来源：bzoj3196 / Tyvj1730 二逼平衡树，在此鸣谢
此数据为洛谷原创。（特别提醒：此数据不保证操作5、6一定存在，故请务必考虑不存在的情况）

题解

我们考虑使用线段树套Splay，即对于线段树中的每一个区间，建一棵Splay维护其中的元素，每次按照线段树的操作依次更新涉及区间。
对于操作1，当区间割裂开的时候不好处理，我们考虑计算严格小于这个数的个数，割裂的两区间的结果加起来就是答案，而排名即这一结果+1。
对于操作2，不好操作，我们二分这个排名为k的数是哪个，因为一旦比这个数字大，肯定大于这个数字的排名，虽然这个数字的排名可能会小于k，但这并不影响二分的正确性。
对于操作3，erase后insert即可。
对于操作4、5，从割裂区间中的结果取min/max即可。
由于自带大常数，只能在O2的帮助下A本题。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

inline int min(int a, int b) {
    return a < b ? a : b;
}

inline int max(int a, int b) {
    return a > b ? a : b;
}

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 50005, INF = 2147483647;

struct Node {
    int fa, ch[2], val, siz, cnt;
} tr[MAXN * 30];

int tot = 0, sta[MAXN], stop = 0; 

inline int newnode() {
    register int p;
    if(stop) p = sta[--stop];
    else p = ++tot;
    memset(tr + p, 0, sizeof(Node));
    return p;
}

inline void delnode(int p) {
    sta[stop++] = p;
}

struct Splay { 
    int rt;

    Splay() {
        rt = 0;
    }

    inline void update(int p) {
        register int lch = tr[p].ch[0], rch = tr[p].ch[1];
        tr[p].siz = tr[lch].siz + tr[rch].siz + tr[p].cnt;
    }

    inline bool isleft(int p) {
        return tr[tr[p].fa].ch[0] == p;
    }

    inline void rotate(int p) {
        register bool t = !isleft(p); register int fa = tr[p].fa, ffa = tr[fa].fa;
        tr[p].fa = ffa; if(ffa) tr[ffa].ch[!isleft(fa)] = p;
        tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
        tr[p].ch[!t] = fa; tr[fa].fa = p;
        update(fa);
        if(!tr[p].fa) rt = p;
    }

    inline void splay(int p, int tar) {
        for(register int fa = tr[p].fa; fa != tar; rotate(p), fa = tr[p].fa) {
            if(tr[fa].fa != tar) rotate(isleft(fa) == isleft(p) ? fa : p);
        }
        update(p);
    }

    inline void insert(int v) {
        if(!rt) {
            rt = newnode();
            tr[rt].val = v;
            tr[rt].siz = tr[rt].cnt = 1;
            return;
        }
        register int p = rt, fa = 0;
        for(;;) {
            if(v == tr[p].val) {
                tr[p].cnt++;
                update(p); update(fa);
                splay(p, 0);
                return;
            }
            fa = p;
            p = tr[p].ch[tr[p].val < v];
            if(!p) {
                p = newnode();
                tr[p].val = v; 
                tr[p].siz = tr[p].cnt = 1;
                tr[p].fa = fa;
                tr[fa].ch[tr[fa].val < v] = p;
                update(fa);
                splay(p, 0);
                return;
            }
        }
    }

    inline int queryrk(int v) {
        register int p = rt, res = 0;
        for(;;) {
            if(v < tr[p].val) {
                p = tr[p].ch[0];
            } else {
                res += tr[tr[p].ch[0]].siz;
                if(v == tr[p].val) {
                    splay(p, 0);
                    return res + 1;
                }
                res += tr[p].cnt;
                p = tr[p].ch[1];
            }
        }
    }

    inline int queryn(int rk) {
        register int p = rt;
        for(;;) {
            if(tr[p].ch[0] && rk <= tr[tr[p].ch[0]].siz) {
                p = tr[p].ch[0];
            } else {
                rk -= tr[tr[p].ch[0]].siz;
                if(rk <= tr[p].cnt) {
                    return tr[p].val;
                }
                rk -= tr[p].cnt;
                p = tr[p].ch[1];
            }
        }
    }
    inline int querypre() {
        register int p = tr[rt].ch[0];
        while(tr[p].ch[1]) p = tr[p].ch[1];
        return p;
    }

    inline int querynxt() {
        register int p = tr[rt].ch[1];
        while(tr[p].ch[0]) p = tr[p].ch[0];
        return p;
    }

    inline void erase(int v) {
        queryrk(v);
        if(tr[rt].cnt > 1) {
            tr[rt].cnt--;
            update(rt);
            return;
        }
        if(!tr[rt].ch[0]) {
            delnode(rt);
            rt = tr[rt].ch[1];
            tr[rt].fa = 0;
            return;
        }
        if(!tr[rt].ch[1]) {
            delnode(rt);
            rt = tr[rt].ch[0];
            tr[rt].fa = 0;
            return;
        }
        register int ort = rt, lmx = querypre();
        splay(lmx, 0);
        tr[rt].ch[1] = tr[ort].ch[1];
        tr[tr[rt].ch[1]].fa = rt;
        delnode(ort);
        update(rt);
    }
} spt[MAXN << 2];

int n, m, a[MAXN];

#define lch o << 1
#define rch (o << 1) | 1
#define mid ((l + r) >> 1)

inline void build(int o, int l, int r) {
    for(register int i = l; i <= r; i++) {
        spt[o].insert(a[i]);
    }
    if(l == r) return;
    build(lch, l, mid);
    build(rch, mid + 1, r);
} 

inline int querybef(int o, int l, int r, int ll, int rr, int k) {
    if(l == ll && r == rr) {
        spt[o].insert(k);
        register int res = spt[o].queryrk(k) - 1;
        spt[o].erase(k);
        return res;
    }
    if(rr <= mid) {
        return querybef(lch, l, mid, ll, rr, k);
    } else if(ll > mid) {
        return querybef(rch, mid + 1, r, ll, rr, k);
    } else {
        return querybef(lch, l, mid, ll, mid, k) + querybef(rch, mid + 1, r, mid + 1, rr, k);
    }
}

inline int queryk(int ll, int rr, int k) {
    register int l = 0, r = 100000001;
    while(r - l > 1) {
        register int rk = querybef(1, 1, n, ll, rr, mid) + 1;
        if(rk <= k) l = mid; else r = mid;
    }
    return l;
}

inline void modify(int o, int l, int r, int x, int w) {
    spt[o].erase(a[x]);
    spt[o].insert(w);
    if(l == r) return;
    if(x <= mid) modify(lch, l, mid, x, w);
    else modify(rch, mid + 1, r, x, w);
}

inline int querypre(int o, int l, int r, int ll, int rr, int k) {
    if(l == ll && r == rr) {
        spt[o].insert(k);
        spt[o].queryrk(k);
        register int res = tr[spt[o].querypre()].val;
        spt[o].erase(k);
        return res ? res : -INF;
    }
    if(rr <= mid) {
        return querypre(lch, l, mid, ll, rr, k);
    } else if(ll > mid) {
        return querypre(rch, mid + 1, r, ll, rr, k);
    } else {
        return max(querypre(lch, l, mid, ll, mid, k), querypre(rch, mid + 1, r, mid + 1, rr, k));
    }
}

inline int querynxt(int o, int l, int r, int ll, int rr, int k) {
    if(l == ll && r == rr) {
        spt[o].insert(k);
        spt[o].queryrk(k);
        register int res = tr[spt[o].querynxt()].val;
        spt[o].erase(k);
        return res ? res : INF;
    }
    if(rr <= mid) {
        return querynxt(lch, l, mid, ll, rr, k);
    } else if(ll > mid) {
        return querynxt(rch, mid + 1, r, ll, rr, k);
    } else {
        return min(querynxt(lch, l, mid, ll, mid, k), querynxt(rch, mid + 1, r, mid + 1, rr, k));
    }
}

int op, l, r, x, k;

int main() {
    n = readint(); m = readint();
    for(register int i = 1; i <= n; i++) {
        a[i] = readint();
    }
    build(1, 1, n);
    while(m--) {
        op = readint(); 
        if(op != 3) {
            l = readint(); r = readint();
        } else {
            x = readint();
        }
        k = readint();
        switch(op) {
        case 1:
            printf("%d\n", querybef(1, 1, n, l, r, k) + 1); break;
        case 2:
            printf("%d\n", queryk(l, r, k)); break;
        case 3:
            modify(1, 1, n, x, k); a[x] = k; break;
        case 4:
            printf("%d\n", querypre(1, 1, n, l, r, k)); break;
        case 5:
            printf("%d\n", querynxt(1, 1, n, l, r, k));
        }
    }
    return 0;
}
Author:
Filed Under: 题解, 算法, 洛谷
Tags: , , , ,

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。