[BZOJ 3169] 二逼平衡树

题目大意

写一种数据结构(可参考题目标题),维护有序数列,支持以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)

解题报告

写的第一道树套树的题。。
这题解法比较多,有线段树套平衡树的,还可以离线主席树，~~据说还有套树状数组的？~~
我用的线段树套Treap(有段时间没写了)
首先使用线段树维护区间,然后每个线段树节点搞一个Treap维护区间内数字的权值,内存开销应该还是N的规模
1.对于第一种操作,排名等于区间内小于k的数数量+1,在线段树上找到询问的区间后到每个区间的Treap里查找k的rank累和就可以了。
2.对于第二中操作,在[0,1e18]内二分一下答案,然后检验就转化成了第一种操作,复杂度貌似爆到$Nlog^3N$。。
3.对于第三种操作,在线段树上找出包含修改的数字的区间然后再每个区间的Treap上暴力删除后再插入即可。
4.对于第四和第五种操作,结合使用第一和第二种操作就可以做出来啦!(懒癌)
思路也比较简单…就直接贴代码了

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
inline int Random () {
    return rand()*rand()*rand();
}
namespace treap {
    const int MAXD = 4000000;
    struct Node {
        int val, ch[2], fa, prio;
        int sz, cnt;
    } d[MAXD];
    int dtot; int * roothandle;
    inline int newNode (int val) {
        dtot ++;
        d[dtot].val = val;
        d[dtot].sz = 1;
        d[dtot].cnt = 1;
        d[dtot].prio = Random();
        return dtot;
    }
    inline void updata (int u) {
        d[u].sz = d[d[u].ch[0]].sz + d[u].cnt + d[d[u].ch[1]].sz;
    }
    inline void rotate (int x) {
        int y = d[x].fa;
        bool f = (d[y].ch[1] == x);
        d[y].ch[f] = d[x].ch[!f];
        d[x].ch[!f] = y;
        d[d[y].ch[f]].fa = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        if(d[x].fa) d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
        else (*roothandle) = x;
        updata(y), updata(x);
    }
    int * src;
    inline int build (int l, int r) {
        if(l > r) return 0;
        int mid = (l+r)>>1;
        int u = newNode(src[mid]);
        int lr = mid-1, rl = mid+1;
        for(; lr >= l && src[lr] == src[mid]; lr--) d[u].sz ++, d[u].cnt ++;
        for(; rl <= r && src[rl] == src[mid]; rl++) d[u].sz ++, d[u].cnt ++;
        d[d[u].ch[0] = build(l, lr)].fa = u;
        d[d[u].ch[1] = build(rl, r)].fa = u;
        updata(u); return u;
    }
    inline int locate (int val, int mov = 0) {
        int u = *roothandle;
        while(u) {
            d[u].sz += mov;
            if(d[u].val == val) return u;
            u = d[u].ch[d[u].val < val];
        }
        return u;
    }
    inline void erase (int u) {
        d[u].cnt --;
        if(d[u].cnt) return ;
        while(d[u].ch[0] || d[u].ch[1])
            if(d[u].ch[0] && (!d[u].ch[1] || d[d[u].ch[0]].prio > d[d[u].ch[1]].prio))
                rotate(d[u].ch[0]);
            else rotate(d[u].ch[1]);
        if(d[u].fa) d[d[u].fa].ch[d[d[u].fa].ch[1] == u] = 0;
    }
    inline void insert (int val) {
        int u = *roothandle, l = 0;
        while(u) {
            l = u; d[u].sz ++;
            if(d[u].val == val) {d[u].cnt ++; return;}
            u = d[u].ch[d[u].val < val];
        }
        u = newNode(val);
        d[u].fa = l;
        d[l].ch[d[l].val < val] = u;
        while(d[u].fa && d[d[u].fa].prio <= d[u].prio) rotate(u);
    }
    inline int getRankByValue (int val) {
        int u = *roothandle, rk = 0;
        while(u) {
            if(d[u].val < val) rk += d[u].cnt + d[d[u].ch[0]].sz, u = d[u].ch[1];
            else if(d[u].val == val) return rk+d[d[u].ch[0]].sz;
            else u = d[u].ch[0];
        }
        return rk;
    }
}
const int MAXN = 51000;
namespace ibt {
    const int MAXD = 400000;
    struct Node {int l, r, uid;} d[MAXD];
    int * src;
    int temp[MAXD];
    void build (int l, int r, int u = 1) {
        d[u].l = l, d[u].r = r;
        int mid = (l+r)>>1;
        for(int i = l; i<=r; i++)
            temp[i] = src[i];
        std :: sort(temp+l, temp+r+1);
        d[u].uid = treap :: build(l, r);
        if(l == r) return ;
        build(l, mid, u<<1), build(mid+1, r, (u<<1)+1);
    }
    int argl, argr, argk, argv;
    inline void fillArgs (int a, int b = 0, int c = 0) {
        argl = a, argr = b, argk = c;
    }
    int getRankByValue (int u = 1) {
        if(d[u].r < argl  || d[u].l > argr ) return 0;
        if(d[u].l >= argl && d[u].r <= argr) {
            treap :: roothandle = &(d[u].uid);
            return treap :: getRankByValue(argk);
        }
        return getRankByValue(u<<1) + getRankByValue((u<<1)+1);
    }
    void modify (int u = 1) {
        if(d[u].r < argl || d[u].l > argr) return ;
        if(d[u].l == d[u].r) {
            argv = treap :: d[d[u].uid].val;
            treap :: d[d[u].uid].val = argk;
            return ;
        }
        modify(u<<1), modify((u<<1)+1);
        treap :: roothandle = &(d[u].uid);
        treap :: erase (treap :: locate(argv, -1));
        treap :: insert(argk);
    }
    int getCnt (int u = 1) {
        if(d[u].r < argl  || d[u].l > argr ) return 0;
        if(d[u].l >= argl && d[u].r <= argr) {
            treap :: roothandle = &(d[u].uid);
            return treap :: d[treap::locate(argk)].cnt;
        }
        return getCnt(u<<1) + getCnt((u<<1)+1);
    }
    int getValueByRank () {
        int lef = 0, rig = 100000000, ans = 0;
        int tmp1 = argk;
        while(lef <= rig) {
            int mid = (lef+rig)>>1; argk = mid;
            int tmp2 = getRankByValue();
            if(tmp2 >= tmp1) rig = mid-1;
            else lef = mid+1, ans = mid;
        }
        return ans;
    }

}
inline int getInt () {
    int ret = 0; char ch; bool f = false;
    while((ch = getchar()) < '0'  || ch > '9' ) f |= (ch == '-');
    ret = ch - '0';
    while((ch = getchar()) >= '0' && ch <= '9') ret *= 10, ret += ch-'0';
    return f ? -ret : ret;
}
int src[MAXN];
int main () {
    int N = getInt(), M = getInt();
    for(int i = 1; i<=N; i++) src[i] = getInt();
    treap :: src = ibt :: temp; ibt :: src = src;
    ibt :: build(1, N);
    for(int i = 1; i<=M; i++) {
        int op = getInt(), a, b, c;
        if(op == 1) {
            a = getInt(), b = getInt(), c = getInt();
            ibt :: fillArgs(a, b, c);
            printf("%d\n", ibt :: getRankByValue()+1);
        } else if(op == 2) {
            a = getInt(), b = getInt(), c = getInt();
            ibt :: fillArgs(a, b, c);
            printf("%d\n", ibt :: getValueByRank());
        } else if(op == 3) {
            a = getInt(), c = getInt();
            ibt :: fillArgs(a, a, c);
            ibt :: modify();
        } else if(op == 4) {
            a = getInt(), b = getInt(), c = getInt();
            ibt :: fillArgs(a, b, c);
            ibt :: argk = ibt :: getRankByValue();
            printf("%d\n", ibt :: getValueByRank());
        } else if(op == 5) {
            a = getInt(), b = getInt(), c = getInt();
            ibt :: fillArgs(a, b, c);
            int tmp = ibt :: getRankByValue();
            ibt :: fillArgs(a, b, c);
            ibt :: argk =  tmp + ibt :: getCnt() + 1;
            printf("%d\n", ibt :: getValueByRank());
        }
    }
}