【模板】二逼平衡树（树套树）【树状数组套线段树】

你的名字 2022-01-10 04:11 299阅读 0赞

[题目描述][Link 1]

被各种毒瘤线段树虐过后突然感觉这道卡了我一万年的树套树很水  
（就一道模板题，不想讲了）  
代码

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstdlib>
    #include<cstring>
    using namespace std;
    const int N=50010, inf=2147483647;
    int n, m, a[N], b[N<<1], cnt;
    int rt[N], idx, ch[N<<8][2], sz[N<<8], xx[N], yy[N], totx, toty;
    #define ls(o) ch[o][1]
    #define rs(o) ch[o][2]
    
    void ins(int &o, int x, int v, int l=1, int r=cnt){
        if(!o) o=++idx; sz[o]+=v; if(l == r) return ; int mid=l+r>>1; 
        if(x <= mid) ins(ls(o), x, v, l, mid); else ins(rs(o), x, v, mid+1, r);
    } 
    void modify(int x, int v){
        int k=lower_bound(b+1, b+cnt+1, a[x])-b;
        for(int i=x; i <= n; i+=i&(-i)) ins(rt[i], k, v);
    }
    
    void getsum(int &sum){
        for(int i=1; i <= totx; i++) sum-=sz[ls(xx[i])]; for(int i=1; i <= toty; i++) sum+=sz[ls(yy[i])];}
    void getls(){
        for(int i=1; i <= totx; i++) xx[i]=ls(xx[i]); for(int i=1; i <= toty; i++) yy[i]=ls(yy[i]);}
    void getrs(){
        for(int i=1; i <= totx; i++) xx[i]=rs(xx[i]); for(int i=1; i <= toty; i++) yy[i]=rs(yy[i]);}
    void prepare(int L, int R){
        for(int i=L-1; i; i-=i&-i) xx[++totx]=rt[i]; for(int i=R; i; i-=i&-i) yy[++toty]=rt[i];}
    int find_kth(int k, int l=1, int r=cnt){
        if(l == r) return l; int mid=l+r>>1, ss=0; getsum(ss);
        if(ss >= k) {getls(); return find_kth(k, l, mid);}
        getrs(); return find_kth(k-ss, mid+1, r);
    }
    void Find_kth(int L, int R, int K){totx=toty=0; prepare(L, R); printf("%d\n", b[find_kth(K)]);}
    
    int get_rank(int o, int x, int l=1, int r=cnt){
        if(!o) return 0; if(l == r) {
        if(x == l) return 0; return sz[o];} int mid=l+r>>1;
        if(x <= mid) return get_rank(ls(o), x, l, mid); return sz[ls(o)]+get_rank(rs(o), x, mid+1, r);
    }
    void Get_rank(int L, int R, int c){
        int ss=0, x=lower_bound(b+1, b+1+cnt, c)-b;
        for(int i=L-1; i; i-=i&-i) ss-=get_rank(rt[i], x);
        for(int i=R; i; i-=i&-i) ss+=get_rank(rt[i], x);
        printf("%d\n", ss+1);
    }
    
    void Get_pre(int L, int R, int c){
        int ss=0, x=lower_bound(b+1, b+1+cnt, c)-b;
        for(int i=L-1; i; i-=i&-i) ss-=get_rank(rt[i], x);
        for(int i=R; i; i-=i&-i) ss+=get_rank(rt[i], x);
        if(!ss) printf("%d\n", -inf);
        else Find_kth(L, R, ss);
    }
    void Get_post(int L, int R, int c){
        int ss=0, x=lower_bound(b+1, b+1+cnt, c)-b+1;
        for(int i=L-1; i; i-=i&-i) ss-=get_rank(rt[i], x);
        for(int i=R; i; i-=i&-i) ss+=get_rank(rt[i], x);
        if(ss > R-L) printf("%d\n", inf);
        else Find_kth(L, R, ss+1);
    }
    
    int read(){
        int out=0, f=1; char c=getchar(); 
        while(c < '0' || c > '9') {
        if(c == '-') f=-1; c=getchar();}
        while(c >= '0' && c <= '9') {out=(out<<1)+(out<<3)+c-'0'; c=getchar();}
        return out*f;
    }
    
    int cmd[N], ql[N], qr[N], qk[N];
    void solve()
    {
        n=read(); m=read();  
        for(int i=1; i <= n; i++) a[i]=read(), b[++cnt]=a[i];
        for(int i=1; i <= m; i++) {
            cmd[i]=read(), ql[i]=read(), qr[i]=read(); 
            if(cmd[i] != 3) qk[i]=read(); 
            if(cmd[i] == 3) b[++cnt]=qr[i];
            else if(cmd[i] != 2) b[++cnt]=qk[i]; 
        }
        sort(b+1, b+cnt+1); cnt=unique(b+1, b+cnt+1)-b-1;
        for(int i=1; i <= n; i++) modify(i, 1);
        for(int i=1; i <= m; i++){
            if(cmd[i] == 1) Get_rank(ql[i], qr[i], qk[i]);
            if(cmd[i] == 2) Find_kth(ql[i], qr[i], qk[i]);
            if(cmd[i] == 3) modify(ql[i], -1), a[ql[i]]=qr[i], modify(ql[i], 1);
            if(cmd[i] == 4) Get_pre(ql[i], qr[i], qk[i]);
            if(cmd[i] == 5) Get_post(ql[i], qr[i], qk[i]);
        }
    }
    
    int main()
    {
        solve();
        return 0;
    }

转载于:https://www.cnblogs.com/zerolt/p/9260878.html

[Link 1]: https://www.luogu.org/problemnew/show/P3380