二逼平衡树

Author Avatar
ZC 2月 02, 2019
  • 在其它设备中阅读本文章

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

讲真,调这题的过程是真的刺激,重构2次,调整6次,最后不得不照着题解抄,才搞出这道题,历时2天多。写题解的人用了22天

题解:

大家好,我非常喜欢暴力数据结构,于是我就用分块过了这道题。

  1. 用一个原数组存储原值,另一个数组使得块内元素排序。$O(nlogn)$
  2. 对于1操作,边角暴力,块内二分。$O(nsqrt(nlogn))$。
  3. 二分,用操作1判断 丧心病狂的操作
  4. 对于3操作,原数组O(1)修改,排序数组修改后重新排序即可。 $O(nsqrt(nlogn))$
  5. 对于4操作,边角暴力,块内二分。 $O(nsqrt(nlogn))$。
  6. 对于5操作,边角暴力,块内二分。 $O(nsqrt(nlogn))$

尽管思路清晰,但还是调了很久

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define Fur(i,x,y) for(int i=x;i<=y;i++)
int MAX(int x,int y){return x>y?x:y;}
int MIN(int x,int y){return x<y?x:y;}
void SWAP(int &x,int &y){x^=y;y^=x;x^=y;}
using namespace std;
#define N 50010
#define mid ((L+R)>>1)
#define midd ((LL+RR)>>1)
int bl[N],le[N],re[N],a[N],s[N],n,m,blk;
template<typename T>
void read(T &x){
    char c=getchar();T p=1;x=0;
    while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }x*=p;
}
void split(){
    int pre=1,prei=0;le[1]=1;
    Fur(i,1,n){
        s[i]=a[i],bl[i]=(i-1)/blk+1;
        if(bl[i]>pre){
            sort(s+prei,s+i);
            pre=bl[i],prei=i;
            le[bl[i]]=i,re[bl[i]-1]=i-1;
        }
    }
    re[bl[n]]=n,sort(s+prei,s+n+1);
}
int key(int l,int r,int x){
    int ans=1,L,R;
    Fur(i,l,MIN(r,re[bl[l]]))if(a[i]<x)++ans;
    Fur(i,bl[l]+1,bl[r]-1)ans+=lower_bound(s+le[i],s+re[i]+1,x)-(s+le[i]);
    if(bl[l]!=bl[r])Fur(i,MAX(l,le[bl[r]]),r)if(a[i]<x)++ans;
    return ans;
}
int find(int l,int r,int x){
    int num,anss=1,L,R,LL=1,RR=1e9;
    while(LL<=RR){
        num=0;
        Fur(i,l,MIN(r,bl[l]*blk))if(a[i]<=midd)++num;
        Fur(i,bl[l]+1,bl[r]-1)num+=upper_bound(s+le[i],s+re[i]+1,midd)-(s+le[i]);
        if(bl[l]!=bl[r])
            Fur(i,MAX(l,le[bl[r]]),r)
                if(a[i]<=midd)++num;
        if(num>=x)anss=midd,RR=midd-1;
        else LL=midd+1;
    }
    return anss;
}
void upd(int pos,int x){
    a[pos]=x;int l=le[bl[pos]],r=re[bl[pos]];
    Fur(i,l,r)s[i]=a[i];
    stable_sort(s+l,s+r+1);
}
int low(int l,int r,int x){
    int ans=-2147483647,L,R;
    Fur(i,l,MIN(r,re[bl[l]]))if(a[i]<x)ans=MAX(ans,a[i]);
    Fur(i,bl[l]+1,bl[r]-1){
        L=le[i],R=re[i];
        while(L<R){
            if(s[mid]>=x)R=mid;
            else L=mid+1;
        }
        if(mid==re[i]){
            if(s[mid]<x)ans=MAX(ans,s[mid]);
            else ans=MAX(ans,s[mid-1]);
        }
        else if(mid!=le[i])ans=MAX(ans,s[mid-1]);
    }
    Fur(i,MAX(l,le[bl[r]]),r)if(a[i]<x)ans=MAX(ans,a[i]);
    return ans;
}
int upp(int l,int r,int x){
    int ans=2147483647,L,R;
    Fur(i,l,MIN(r,re[bl[l]]))if(a[i]>x)ans=MIN(ans,a[i]);
    Fur(i,bl[l]+1,bl[r]-1){
        L=le[i],R=re[i];
        while(L<R){
            if(s[mid]>x)R=mid;
            else L=mid+1;
        }
        if(mid==re[i]&&s[mid]<=x)continue;
        ans=MIN(ans,s[mid]);
    }
    Fur(i,MAX(l,le[bl[r]]),r)if(a[i]>x)ans=MIN(ans,a[i]);
    return ans;
}
int main(){
    int opt,x,y,k;
    scanf("%d%d",&n,&m);
    Fur(i,1,n)read(a[i]);blk=sqrt(n);
    split();
    Fur(i,1,m){
        read(opt),read(x),read(y);
        if(opt==1)read(k),printf("%d\n",key(x,y,k));
        if(opt==2)read(k),printf("%d\n",find(x,y,k));
        if(opt==3)upd(x,y);
        if(opt==4)read(k),printf("%d\n",low(x,y,k));
        if(opt==5)read(k),printf("%d\n",upp(x,y,k));
    }
}

`