BZOJ 3196: Tyvj 1730 二逼平衡树 [树套树]

题解不会写,标记一下,抄的是同学的板子

#include<cstdio>
#include<algorithm>
#define N 50010
#define M N*30
using namespace std;

int n,m,sz,ans,a[N],root[M],size[M],fa[M],ch[M][],v[M];

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

inline int read(){
    int a=;char c=nc(),f=;
    while(c<'0'||c>'9'){if(c=='-')f=-;c=nc();}
    while(c>='0'&&c<='9'){a=a*10+c-'0';c=nc();}
    return a*f;
}

inline int get(int x){return ch[fa[x]][]==x;}

inline void update(int x){
    if(x){
    size[x]=;
    if(ch[x][]) size[x]+=size[ch[x][]];
    if(ch[x][]) size[x]+=size[ch[x][]];
    }
}

inline void rotate(int x){
    int y=fa[x],opt=(ch[y][]==x);
    ch[y][opt]=ch[x][opt^];
    if(ch[x][opt^]) fa[ch[x][opt^]]=y;
    if(fa[x]=fa[y]) ch[fa[y]][ch[fa[y]][]==y]=x;
    fa[y]=x,ch[x][opt^]=y;
    update(y),update(x);
}

inline void splay(int x,int ed,int pos){
    for(int fat=fa[x];fat!=ed;rotate(x),fat=fa[x])
    if(fa[fat]!=ed) rotate((x==ch[fat][])==(fat==ch[fa[fat]][])?fat:x);
    if(!ed) root[pos]=x;
}

inline void insert(int rt,int x){
    int nw=root[rt];
    while(ch[nw][v[nw]<x]) nw=ch[nw][v[nw]<x];
    v[++sz]=x,fa[sz]=nw,ch[sz][]=ch[sz][]=;
    if(nw) ch[nw][v[nw]<x]=sz;
    splay(sz,,rt);
}

inline int srank(int rt,int x){
    int nw=root[rt],ans=;
    while(nw)
    if(v[nw]<x) ans+=size[ch[nw][]]+,nw=ch[nw][];
    else nw=ch[nw][];
    return ans;
}

inline void del(int rt,int x){
    int nw=root[rt];
    while(v[nw]!=x) nw=ch[nw][v[nw]<x];
    splay(nw,,rt);
    if(!ch[root[rt]][]){
    fa[root[rt]=ch[root[rt]][]]=;
    return;
    }
    nw=ch[root[rt]][];
    while(ch[nw][]) nw=ch[nw][];
    splay(nw,root[rt],rt);
    fa[ch[nw][]=ch[root[rt]][]]=nw,fa[root[rt]=nw]=;
    update(nw);
    return;
}

inline void spre(int rt,int x){
    int nw=root[rt];
    while(nw)
    if(v[nw]<x) ans=max(ans,v[nw]),nw=ch[nw][];
    else nw=ch[nw][];
}

inline void ssuf(int rt,int x){
    int nw=root[rt];
    while(nw)
    if(x<v[nw]) ans=min(ans,v[nw]),nw=ch[nw][];
    else nw=ch[nw][];
}

#define ls (x<<1)
#define rs (x<<1|1)
#define mid (l+r>>1)

void change(int x,int l,int r,int q,int v,int opt){
    if(opt) insert(x,v);
    else del(x,v);
    if(l==r) return;
    if(q<=mid) change(ls,l,mid,q,v,opt);
    else change(rs,mid+1,r,q,v,opt);
}

inline int rank(int x,int l,int r,int ql,int qr,int v){
    if(l>qr||r<ql) return ;
    if(l>=ql&&r<=qr) return srank(x,v);
    return rank(ls,l,mid,ql,qr,v)+rank(rs,mid+,r,ql,qr,v);
}

inline void pre(int x,int l,int r,int ql,int qr,int v){
    if(l>qr||r<ql) return;
    if(l>=ql&&r<=qr) return spre(x,v);
    pre(ls,l,mid,ql,qr,v),pre(rs,mid+,r,ql,qr,v);
}

inline void suf(int x,int l,int r,int ql,int qr,int v){
    if(l>qr||r<ql) return;
    if(l>=ql&&r<=qr) return ssuf(x,v);
    suf(ls,l,mid,ql,qr,v),suf(rs,mid+,r,ql,qr,v);
}

inline long long find(int x,int y,int k){
    long long l=,r=e9;
    while(l<=r)
    if(rank(,,n,x,y,mid)+<=k) l=mid+;
    else r=mid-;
    return r;
}

int main(){
    n=read(),m=read();
    for(int i=;i<=n;++i) a[i]=read(),change(,,n,i,a[i],);
    while(m--){
    int opt=read(),l,r,k,pos;
    switch(opt){
    case :l=read(),r=read(),k=read();printf("%d\n",rank(,,n,l,r,k)+);break;
    case :l=read(),r=read(),k=read();printf("%d\n",find(l,r,k));break;
    case :pos=read(),k=read();change(,,n,pos,a[pos],),change(,,n,pos,a[pos]=k,);break;
    case :l=read(),r=read(),k=read();ans=-(ll<<)+,pre(,,n,l,r,k);printf("%d\n",ans);break;
    case :l=read(),r=read(),k=read();ans=(ll<<)-,suf(,,n,l,r,k);printf("%d\n",ans);break;
    }
    }
    return ;
}