BZOJ 3196 线段树套平衡树

心已赠人 2021-12-22 14:13 256阅读 0赞

（代码无比丑陋）

//By SiriusRen
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int n,m,L,R,xx,tx,t,root[3000050],size,ans,op,inf=0x3fffffff,a[500050];
    struct Treap{
         int ch[2],v,cnt,sz,rnd;}tr[3000050];
    void Upd(int k){
         tr[k].sz=tr[tr[k].ch[0]].sz+tr[tr[k].ch[1]].sz+tr[k].cnt;}
    void rot(int &k,bool f){
         int t=tr[k].ch[f];tr[k].ch[f]=tr[t].ch[!f],tr[t].ch[!f]=k,Upd(k),Upd(t),k=t;}
    void ins(int &k){
        if(!k){k=++size;tr[k].v=xx;tr[k].cnt=tr[k].sz=1;tr[k].rnd=rand();return;}
        tr[k].sz++;
        if(tr[k].v==xx){
         tr[k].cnt++;return;}
        bool f=xx>tr[k].v;ins(tr[k].ch[f]);
        if(tr[tr[k].ch[f]].rnd<tr[k].rnd)rot(k,f);
    }
    void del(int &k){
        if(tr[k].v==tx){
            if(tr[k].cnt>1)tr[k].cnt--,tr[k].sz--;
            else if(tr[k].ch[0]*tr[k].ch[1]==0)k=tr[k].ch[0]+tr[k].ch[1];
            else rot(k,tr[tr[k].ch[0]].rnd>=tr[tr[k].ch[1]].rnd),del(k);
        }
        else tr[k].sz--,del(tr[k].ch[tx>tr[k].v]);
    }
    void rank(int k){
        if(!k)return;
        if(tr[k].v==xx)ans+=tr[tr[k].ch[0]].sz;
        else if(tr[k].v>xx)rank(tr[k].ch[0]);
        else ans+=tr[tr[k].ch[0]].sz+tr[k].cnt,rank(tr[k].ch[1]);
    }
    void query(int k){
        if(!k)return;
        if(op==4&&tr[k].v<xx)ans=max(ans,tr[k].v),query(tr[k].ch[1]);
        else if(op==4)query(tr[k].ch[0]);
        else if(op==5&&tr[k].v>xx)ans=min(ans,tr[k].v),query(tr[k].ch[0]);
        else query(tr[k].ch[1]);
    }
    void Build(int l,int r,int pos){
        ins(root[pos]);if(l==r)return;
        int mid=(l+r)>>1;
        if(mid<t)Build(mid+1,r,pos<<1|1);
        else Build(l,mid,pos<<1);
    }
    void Rank(int l,int r,int pos){
        if(l>=L&&r<=R){rank(root[pos]);return;}
        int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
        if(mid<L)Rank(mid+1,r,rson);
        else if(mid>=R)Rank(l,mid,lson);
        else Rank(l,mid,lson),Rank(mid+1,r,rson);
    }
    void Change(int l,int r,int pos){
        del(root[pos]),ins(root[pos]);
        if(l==r)return;
        int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
        if(mid<t)Change(mid+1,r,rson);
        else Change(l,mid,lson); 
    }
    void Ask(int l,int r,int pos){
        if(l>=L&&r<=R){query(root[pos]);return;}
        int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
        if(mid<L)Ask(mid+1,r,rson);
        else if(mid>=R)Ask(l,mid,lson);
        else Ask(l,mid,lson),Ask(mid+1,r,rson);
    }
    void b_srch(){
        int l=0,r=inf,Ans=0;
        while(l<=r){
            ans=1,xx=(l+r)>>1,Rank(1,n,1);
            if(ans<=tx)Ans=xx,l=xx+1;
            else r=xx-1;
        }
        printf("%d\n",Ans);
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(t=1;t<=n;t++)scanf("%d",&a[t]),xx=a[t],Build(1,n,1);
        while(m--){
            scanf("%d",&op);
            if(op!=3){
                scanf("%d%d%d",&L,&R,&xx);
                if(op==1)ans=1,Rank(1,n,1),printf("%d\n",ans);
                else if(op==2)tx=xx,b_srch();
                else{
                    ans=inf;if(op==4)ans=0;Ask(1,n,1);
                    printf("%d\n",ans);
                }
            }
            else scanf("%d%d",&t,&xx),tx=a[t],Change(1,n,1),a[t]=xx;
        }
    }

转载于:https://www.cnblogs.com/SiriusRen/p/6532159.html