zcmimi's blog
avatar
zc
2020-03-27 20:17:00
  • 本文总阅读量
查看原题

点击跳转

此题非常之毒瘤,我写的整个人都二逼了

共有一下几种解法:

  1. 树状数组套线段树
  2. 线段树套平衡树
  3. 权值线段树套平衡树
  4. 分块
  5. 整体二分

树状数组套线段树

离散化+树状数组套动态开点线段树

这应该是一种常数小又好写的方法了,不开o2也轻松过

可以参照LG 2617 Dynamic Rankings的做法

简要说下思路:

树状数组记录位置,权值线段树记录权值

树状数组的每个节点都是一颗权值线段树

  1. 查询区间内一个数的排名:

    在树状数组上找到区间对应的节点,对应的权值线段树线段树树内查询对应数的排名并求和。

  2. 查询区间内排名为k的数是几:

    找出树状数组中所有对应节点,然后权值线段树上二分(与主席树的方法相似)

  3. 单点修改:

    相当于树状数组上的单点修改,在对应节点的权值线段树中删除原数,加入新数

  4. 前驱:

    查询排名,然后找排名-1的数

  5. 后继:

    查询排名,然后找排名+1的数

语文不好,不大会表述,相信数据结构这种东西直接看代码更好理解

具体可以看代码

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
#define fur(i,x,y) for(int i=x;i<=y;++i)
namespace IN{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;inline char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>inline void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>inline void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IN;
namespace OUT{const char ln='\n';const int str=1<<20;static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;inline void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}inline void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}inline void out(char c){pt(c);}template<typename T>inline void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>inline void out(T x,arr & ... y){out(x),out(y...);}}using namespace OUT;
#define N 50011
int n,q,tot,sz,a[N],c[N<<1],RT[N],s[N*400],ls[N*400],rs[N*400];
struct que{int opt,l,r,k;}Q[N];
struct node{int v,id,typ;bool operator<(node t)const{return v<t.v;}}b[N<<1];
void upd(int x,int v,int l,int r,int &rt){
    if(!rt)rt=++sz;
    s[rt]+=v;
    if(l==r){return;}
    int m=l+r>>1;
    if(x<=m)upd(x,v,l,m,ls[rt]);
    else upd(x,v,m+1,r,rs[rt]);
}
il void UPD(int x,int v){for(int i=x;i<=n;i+=i&-i)upd(a[x],v,1,tot,RT[i]);}
int tl[20],tr[20];
il int rnk(int l,int r,int v,int t=0){//还是二分,加了个特判(可以是这个数的第一个或最后一个的排名)
    int cl=0,cr=0,m,res=0;
    //获取区间对应的所有根节点位置
    for(int i=l-1;i;i^=i&-i)tl[++cl]=RT[i];
    for(int i=r;i;i^=i&-i)tr[++cr]=RT[i];
    l=1,r=tot;
    while(l<r){
        m=l+r>>1;
        if(v+t<=m){ //比mid小,进入左儿子  (t为特判)
            fur(i,1,cl)tl[i]=ls[tl[i]];
            fur(i,1,cr)tr[i]=ls[tr[i]];
            r=m;
        }
        else{ //进入右儿子
            fur(i,1,cl)res-=s[ls[tl[i]]],tl[i]=rs[tl[i]];
            fur(i,1,cr)res+=s[ls[tr[i]]],tr[i]=rs[tr[i]];
            l=m+1;
        }
    }
    return res+1-t;
}
il int kth(int l,int r,int k){// 与Dynamic Rankings一样,二分
    int cl=0,cr=0,cnt,m;
    for(int i=l-1;i;i^=i&-i)tl[++cl]=RT[i];
    for(int i=r;i;i^=i&-i)tr[++cr]=RT[i];
    l=1,r=tot;
    while(l<r){
        m=l+r>>1;cnt=0;
        fur(i,1,cl)cnt-=s[ls[tl[i]]];
        fur(i,1,cr)cnt+=s[ls[tr[i]]];
        if(k<=cnt){
            fur(i,1,cl)tl[i]=ls[tl[i]];
            fur(i,1,cr)tr[i]=ls[tr[i]];
            r=m;
        }
        else{
            fur(i,1,cl)tl[i]=rs[tl[i]];
            fur(i,1,cr)tr[i]=rs[tr[i]];
            k-=cnt,l=m+1;
        }
    }
    return c[l];
}
il int pre(int l,int r,int k){//求出 排名 后求 排名-1 的数
    int t=rnk(l,r,k)-1;
    if(!t)return -2147483647;
    return kth(l,r,t);
}
il int nxt(int l,int r,int k){//类似前驱
    int t=rnk(l,r,k,1)+1;
    if(t==r-l+2)return 2147483647;
    return kth(l,r,t);
}
int main(){
    in(n,q);
    int opt,l,r,k,d=n,t=0,x;
    fur(i,1,n)in(x),b[i]={x,i,0};
    fur(i,1,q){
        in(opt,l,r);
        if(opt==3)k=r;
        else in(k);
        Q[i]=que{opt,l,r,k};
        if(opt!=2)b[++d]=node{k,i,1};
    }
    //离散化,统一离散化较快,如果要方便话可以像其他题解一样使用lowerbound
    std::sort(b+1,b+d+1);b[0].v=-(1<<30);
    fur(i,1,d)c[(b[i].typ?Q[b[i].id].k:a[b[i].id])=tot+=b[i].v!=b[i-1].v]=b[i].v;
    fur(i,1,n)UPD(i,1);
    fur(i,1,q){
        opt=Q[i].opt;l=Q[i].l,r=Q[i].r,k=Q[i].k;
        if(opt==1)out(rnk(l,r,k),ln);
        if(opt==2)out(kth(l,r,k),ln);
        if(opt==3)UPD(l,-1),a[l]=k,UPD(l,1);
        if(opt==4)out(pre(l,r,k),ln);
        if(opt==5)out(nxt(l,r,k),ln);
    }
    flush();
}

线段树套平衡树

最经典的解法

  1. 查询区间内一个数的排名:

    在线段树上找到区间对应的节点,然后每个节点的平衡树内查询对应数的排名并求和。

  2. 查询区间内排名为k的数是几:

    这项操作在线段树上不可加,只能退一步

    二分答案,用操作1判断

  3. 单点修改:

    在线段树上找到所有覆盖这个点的区间,然后在所有区间对应的平衡树中删除原数,加入新数

  4. 前驱:

    在线段树上找到该区间对应的节点,对 这些节点求得的前驱 取min

  5. 同4

这里的平衡树采用常数小且好写的treap

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
#define fur(i,x,y) for(int i=x;i<=y;++i)
il int min(int x,int y){return x<y?x:y;}
il int max(int x,int y){return x>y?x:y;}
namespace IN{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;inline char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>inline void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>inline void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IN;
namespace OUT{const char ln='\n';const int str=1<<20;static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;inline void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}inline void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}inline void out(char c){pt(c);}template<typename T>inline void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>inline void out(T x,arr & ... y){out(x),out(y...);}}using namespace OUT;
const int N=50011,inf=2147483647,M=3000001;
int n,q,cnt,a[N],RT[N*20],rnd[M],c[M][2],s[M],val[M];
il int rand(){static int seed=233;return seed=(int)seed*482711LL%inf;}
il void pu(int x){s[x]=s[c[x][0]]+s[c[x][1]]+1;}
il void turn(int &x,int p){
    int t=c[x][p];
    c[x][p]=c[t][!p];
    c[t][!p]=x;
    pu(x);pu(x=t);
}
void ins(int &x,int v){
    if(!x){s[x=++cnt]=1;val[x]=v;rnd[x]=rand();return;}
    ++s[x];
    int p=(v>val[x]);
    ins(c[x][p],v);
    if(rnd[c[x][p]]<rnd[x])turn(x,p);
}
void del(int &x,int v){
    if(val[x]==v){
        if(!c[x][0]||!c[x][1]){x=c[x][0]|c[x][1];return;}
        int p=rnd[c[x][0]]>rnd[c[x][1]];
        turn(x,p);del(c[x][!p],v);
    }
    else del(c[x][v>=val[x]],v);
    pu(x);
}
int rnk(int x,int v){
    if(!x)return 0;
    if(v<=val[x])return rnk(c[x][0],v);
    return s[c[x][0]]+1+rnk(c[x][1],v);
}
int pre(int x,int v){
    if(!x)return -inf;
    if(v>val[x])return max(val[x],pre(c[x][1],v));
    else return pre(c[x][0],v);
}
int nxt(int x,int v){
    if(!x)return inf;
    if(v<val[x])return min(val[x],nxt(c[x][0],v));
    else return nxt(c[x][1],v);
}
#define ls rt<<1
#define rs rt<<1|1
void build(int p,int v,int l=1,int r=n,int rt=1){
    ins(RT[rt],v);
    if(l==r)return;
    int m=l+r>>1;
    if(p<=m)build(p,v,l,m,ls);
    else build(p,v,m+1,r,rs);
}
void upd(int p,int v,int l=1,int r=n,int rt=1){
    del(RT[rt],a[p]);ins(RT[rt],v);
    if(l==r)return;
    int m=l+r>>1;
    if(p<=m)upd(p,v,l,m,ls);
    else upd(p,v,m+1,r,rs);
}
int RNK(int L,int R,int v,int l=1,int r=n,int rt=1){
    if(L<=l&&r<=R)return rnk(RT[rt],v);
    int m=l+r>>1,ans=0;
    if(L<=m)ans=RNK(L,R,v,l,m,ls);
    if(R>m)ans+=RNK(L,R,v,m+1,r,rs);
    return ans;
}
int KTH(int L,int R,int k){
    int l=0,r=1e8,m,ans;
    while(l<=r){
        m=l+r>>1;
        if(RNK(L,R,m)+1<=k)l=m+1,ans=m;
        else r=m-1;
    }
    return ans;
}
int PRE(int L,int R,int v,int l=1,int r=n,int rt=1){
    if(L<=l&&r<=R)return pre(RT[rt],v);
    int m=l+r>>1,ans=-inf;
    if(L<=m)ans=PRE(L,R,v,l,m,ls);
    if(R>m)ans=max(ans,PRE(L,R,v,m+1,r,rs));
    return ans;
}
int NXT(int L,int R,int v,int l=1,int r=n,int rt=1){
    if(L<=l&&r<=R)return nxt(RT[rt],v);
    int m=l+r>>1,ans=inf;
    if(L<=m)ans=NXT(L,R,v,l,m,ls);
    if(R>m)ans=min(ans,NXT(L,R,v,m+1,r,rs));
    return ans;
}
int main(){
    in(n,q);
    fur(i,1,n)in(a[i]),build(i,a[i]);
    int opt,l,r,k;
    fur(i,1,q){
        in(opt,l,r);
        if(opt==3)upd(l,r),a[l]=r;
        else in(k);
        if(opt==1)out(RNK(l,r,k)+1,ln);
        if(opt==2)out(KTH(l,r,k),ln);
        if(opt==4)out(PRE(l,r,k),ln);
        if(opt==5)out(NXT(l,r,k),ln);
    }
    flush();
}

权值线段树套平衡树

换个思路,权值线段树外层记录权值,内层记录位置

整体二分

分块

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
#define fur(i,x,y) for(int i=x;i<=y;++i)
namespace IN{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;inline char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>inline void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>inline void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IN;
namespace OUT{const char ln='\n';const int str=1<<20;static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;inline void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}inline void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}inline void out(char c){pt(c);}template<typename T>inline void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>inline void out(T x,arr & ... y){out(x),out(y...);}}using namespace OUT;
#define N 50011
int n,q,tot,sz,a[N],c[N<<1],RT[N],s[N*400],ls[N*400],rs[N*400];
struct que{int opt,l,r,k;}Q[N];
struct node{int v,id,typ;bool operator<(node t)const{return v<t.v;}}b[N<<1];
void upd(int x,int v,int l,int r,int &rt){
    if(!rt)rt=++sz;
    s[rt]+=v;
    if(l==r){return;}
    int m=l+r>>1;
    if(x<=m)upd(x,v,l,m,ls[rt]);
    else upd(x,v,m+1,r,rs[rt]);
}
il void UPD(int x,int v){for(int i=x;i<=n;i+=i&-i)upd(a[x],v,1,tot,RT[i]);}
int tl[20],tr[20];
il int rnk(int l,int r,int v,int t=0){//还是二分,加了个特判(可以是这个数的第一个或最后一个的排名)
    int cl=0,cr=0,m,res=0;
    //获取区间对应的所有根节点位置
    for(int i=l-1;i;i^=i&-i)tl[++cl]=RT[i];
    for(int i=r;i;i^=i&-i)tr[++cr]=RT[i];
    l=1,r=tot;
    while(l<r){
        m=l+r>>1;
        if(v+t<=m){ //比mid小,进入左儿子  (t为特判)
            fur(i,1,cl)tl[i]=ls[tl[i]];
            fur(i,1,cr)tr[i]=ls[tr[i]];
            r=m;
        }
        else{ //进入右儿子
            fur(i,1,cl)res-=s[ls[tl[i]]],tl[i]=rs[tl[i]];
            fur(i,1,cr)res+=s[ls[tr[i]]],tr[i]=rs[tr[i]];
            l=m+1;
        }
    }
    return res+1-t;
}
il int kth(int l,int r,int k){// 与Dynamic Rankings一样,二分
    int cl=0,cr=0,cnt,m;
    for(int i=l-1;i;i^=i&-i)tl[++cl]=RT[i];
    for(int i=r;i;i^=i&-i)tr[++cr]=RT[i];
    l=1,r=tot;
    while(l<r){
        m=l+r>>1;cnt=0;
        fur(i,1,cl)cnt-=s[ls[tl[i]]];
        fur(i,1,cr)cnt+=s[ls[tr[i]]];
        if(k<=cnt){
            fur(i,1,cl)tl[i]=ls[tl[i]];
            fur(i,1,cr)tr[i]=ls[tr[i]];
            r=m;
        }
        else{
            fur(i,1,cl)tl[i]=rs[tl[i]];
            fur(i,1,cr)tr[i]=rs[tr[i]];
            k-=cnt,l=m+1;
        }
    }
    return c[l];
}
il int pre(int l,int r,int k){//求出 排名 后求 排名-1 的数
    int t=rnk(l,r,k)-1;
    if(!t)return -2147483647;
    return kth(l,r,t);
}
il int nxt(int l,int r,int k){//类似前驱
    int t=rnk(l,r,k,1)+1;
    if(t==r-l+2)return 2147483647;
    return kth(l,r,t);
}
int main(){
    in(n,q);
    int opt,l,r,k,d=n,t=0,x;
    fur(i,1,n)in(x),b[i]={x,i,0};
    fur(i,1,q){
        in(opt,l,r);
        if(opt==3)k=r;
        else in(k);
        Q[i]=que{opt,l,r,k};
        if(opt!=2)b[++d]=node{k,i,1};
    }
    //离散化,统一离散化较快,如果要方便话可以像其他题解一样使用lowerbound
    std::sort(b+1,b+d+1);b[0].v=-(1<<30);
    fur(i,1,d)c[(b[i].typ?Q[b[i].id].k:a[b[i].id])=tot+=b[i].v!=b[i-1].v]=b[i].v;
    fur(i,1,n)UPD(i,1);
    fur(i,1,q){
        opt=Q[i].opt;l=Q[i].l,r=Q[i].r,k=Q[i].k;
        if(opt==1)out(rnk(l,r,k),ln);
        if(opt==2)out(kth(l,r,k),ln);
        if(opt==3)UPD(l,-1),a[l]=k,UPD(l,1);
        if(opt==4)out(pre(l,r,k),ln);
        if(opt==5)out(nxt(l,r,k),ln);
    }
    flush();
}
LG 3380 【模板】二逼平衡树(树套树)
comment评论
Search
search