BZOJ3065:带插入区间K小值 ScapegoatTree套动态开点线段树

题目大意:

见题目标题.

思路:

外层用替罪羊树维护元素之间的相对位置,每个替罪羊树节点维护一颗权值线段树表示以该节点为根的子树内所有的权值组成的线段树.

如此,对于询问\([l,r]\),我们先找出构成前\(l-1\)个元素的替罪羊树节点,再找出构成前\(r\)个元素的替罪羊树节点.随后在上面仿照主席树一样走一下.这个过程是\(O(log^2n)\)的.

对于插入,首先在替罪羊树上暴力插入,随后找到插入位置不满足平衡条件的深度最大的祖先,并暴力重构以该祖先为根的子树.根据均摊分析,每次插入的复杂度为\(O(log^2n)\).

对于修改,我们只需在替罪羊树上的沿途节点的线段树上进行单点修改即可.时间复杂度\(O(log^2n)\).

这样我们就用\(O(mlog^2n)\)的复杂度解决了此题.

(推荐去看VFK的系列题解,这里只是流水帐罢了...)

#include<stack>
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc())&&c!='-');bool sign=c=='-';
        x=sign?0:c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
        if(sign)x=-x;
    }
    inline char Getch(){
        char c;while((c=getc())!='Q'&&c!='M'&&c!='I');return c;
    }
    char buf[400000],*o=buf;
    template<typename T>inline void Print(T x){
        static int stk[100];int top=0;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void Final(){fwrite(buf,1,o-buf,stdout);}
}
 
typedef double f2;
static const f2 Alpha=0.8;
 
#define N 70010
 
#define Segl(x) SegMemPool[x].l
#define Segr(x) SegMemPool[x].r
#define Segsiz(x) SegMemPool[x].siz
struct SegNode{
    int l,r,siz;
}SegMemPool[20000000];int Segid;
stack<int>SegNodeTrashBin;
int NewSegNode(){
    static int res;
    if(SegNodeTrashBin.size()!=0)res=SegNodeTrashBin.top(),SegNodeTrashBin.pop();
    else res=++Segid;
    Segl(res)=Segr(res)=Segsiz(res)=0;
    return res;
}
inline void Modify(int tl,int tr,int ins,int d,int&q){
    if(!q)q=NewSegNode();Segsiz(q)+=d;
    if(tl==tr)return;
    int mid=(tl+tr)>>1;
    if(ins<=mid)Modify(tl,mid,ins,d,Segl(q));else Modify(mid+1,tr,ins,d,Segr(q));
}
 
#define Scapel(x) ScapeMemPool[x].l
#define Scaper(x) ScapeMemPool[x].r
#define Scapesiz(x) ScapeMemPool[x].siz
#define ScapeRoot(x) ScapeMemPool[x].SegRoot
#define ScapeVal(x) ScapeMemPool[x].v
struct ScapeNode{
    int l,r,siz,v,SegRoot;
}ScapeMemPool[8000000];int Scapeid,ScapeTreeRoot;
stack<int>ScapeNodeTrashBin;
inline f2 Priority(int q){
    return Max(Scapesiz(Scapel(q)),Scapesiz(Scaper(q)))/(f2)Scapesiz(q);
}
int NewScapeNode(){
    static int res;
    if(ScapeNodeTrashBin.size()!=0)res=ScapeNodeTrashBin.top(),ScapeNodeTrashBin.pop();
    else res=++Scapeid;
    Scapel(res)=Scaper(res)=Scapesiz(res)=ScapeRoot(res)=ScapeVal(res)=0;
    return res;
}
 
#define MaxRange 70000
int seq[N],dfn;
void Build(int tl,int tr,int&q){
    if(tl>tr)return;
    int mid=(tl+tr)>>1;
    if(!q)q=NewScapeNode();ScapeVal(q)=seq[mid];
    for(int i=tl;i<=tr;++i)Modify(0,MaxRange,seq[i],1,ScapeRoot(q));
    if(tl^tr)Build(tl,mid-1,Scapel(q)),Build(mid+1,tr,Scaper(q));
    Scapesiz(q)=Scapesiz(Scapel(q))+1+Scapesiz(Scaper(q));
}
 
 
int ReBuildLabel;
void SegNodeIntoTrash(int q){
    if(Segl(q))SegNodeIntoTrash(Segl(q));
    if(Segr(q))SegNodeIntoTrash(Segr(q));
    SegNodeTrashBin.push(q);
}
void ScapeNodeIntoTrash(int q){
    if(Scapel(q))ScapeNodeIntoTrash(Scapel(q));
    ScapeNodeTrashBin.push(q);
    seq[++dfn]=ScapeVal(q);SegNodeIntoTrash(ScapeRoot(q)),ScapeRoot(q)=0;
    if(Scaper(q))ScapeNodeIntoTrash(Scaper(q));
}
inline void ReBuild(int q){
    dfn=0;
    if(Scapel(q))ScapeNodeIntoTrash(Scapel(q)),Scapel(q)=0;
    SegNodeIntoTrash(ScapeRoot(q)),ScapeRoot(q)=0;seq[++dfn]=ScapeVal(q);
    if(Scaper(q))ScapeNodeIntoTrash(Scaper(q)),Scaper(q)=0;
    Build(1,dfn,q);
}
inline void InsertValue(int&q,int ins,int _v){
    if(!q){
        q=NewScapeNode();
        Modify(0,MaxRange,_v,1,ScapeRoot(q));
        Scapesiz(q)=1;
        ScapeVal(q)=_v;
        return;
    }
    else{
        Modify(0,MaxRange,_v,1,ScapeRoot(q));
        if(ins<=Scapesiz(Scapel(q))+1)InsertValue(Scapel(q),ins,_v);
        else InsertValue(Scaper(q),ins-Scapesiz(Scapel(q))-1,_v);
        Scapesiz(q)=Scapesiz(Scapel(q))+1+Scapesiz(Scaper(q));
        if(Priority(q)>Alpha&&!ReBuildLabel)ReBuildLabel=q;
    }
}
inline void GlobalInsertValue(int ins,int _v){
    ReBuildLabel=0;
    InsertValue(ScapeTreeRoot,ins,_v);
    if(ReBuildLabel)ReBuild(ReBuildLabel);
}
 
int seql[100],cntl,seqr[100],cntr,vall[100],sizl,valr[100],sizr;
inline void SetInQueue(int q,int ins,int seq[],int&cnt,int val[],int&siz){
    if(!q)return;
    if(ins<Scapesiz(Scapel(q)))SetInQueue(Scapel(q),ins,seq,cnt,val,siz);
    else if(ins==Scapesiz(Scapel(q)))seq[++cnt]=ScapeRoot(Scapel(q));
    else if(ins==Scapesiz(Scapel(q))+1)seq[++cnt]=ScapeRoot(Scapel(q)),val[++siz]=ScapeVal(q);
    else if(ins>Scapesiz(Scapel(q))+1)seq[++cnt]=ScapeRoot(Scapel(q)),val[++siz]=ScapeVal(q),SetInQueue(Scaper(q),ins-Scapesiz(Scapel(q))-1,seq,cnt,val,siz);
}
inline int GlobalQuery(int tl,int tr,int kth){
    cntl=cntr=sizl=sizr=0;
    if(tl-1)SetInQueue(ScapeTreeRoot,tl-1,seql,cntl,vall,sizl);
    SetInQueue(ScapeTreeRoot,tr,seqr,cntr,valr,sizr);
 
    int L=0,R=MaxRange,mid,ls,i;
    while(L<R){
        mid=(L+R)>>1;
        ls=0;
        for(i=1;i<=cntl;++i)ls-=Segsiz(Segl(seql[i]));
        for(i=1;i<=cntr;++i)ls+=Segsiz(Segl(seqr[i]));
        for(i=1;i<=sizl;++i)if(vall[i]>=L&&vall[i]<=mid)--ls;
        for(i=1;i<=sizr;++i)if(valr[i]>=L&&valr[i]<=mid)++ls;
        if(kth<=ls){
            for(i=1;i<=cntl;++i)seql[i]=Segl(seql[i]);
            for(i=1;i<=cntr;++i)seqr[i]=Segl(seqr[i]);
            R=mid;
        }
        else{
            for(i=1;i<=cntl;++i)seql[i]=Segr(seql[i]);
            for(i=1;i<=cntr;++i)seqr[i]=Segr(seqr[i]);
            kth-=ls,L=mid+1;
        }
    }return L;
}
 
void ScapeModify(int q,int ins,int pre,int to){
    Modify(0,MaxRange,pre,-1,ScapeRoot(q)),Modify(0,MaxRange,to,1,ScapeRoot(q));
    if(ins<=Scapesiz(Scapel(q)))ScapeModify(Scapel(q),ins,pre,to);
    else if(ins==Scapesiz(Scapel(q))+1){ScapeVal(q)=to;return;}
    else ScapeModify(Scaper(q),ins-Scapesiz(Scapel(q))-1,pre,to);
}
int AskScapeVal(int q,int ins){
    if(ins<=Scapesiz(Scapel(q)))return AskScapeVal(Scapel(q),ins);
    else if(ins==Scapesiz(Scapel(q))+1)return ScapeVal(q);
    else return AskScapeVal(Scaper(q),ins-Scapesiz(Scapel(q))-1);
}
 
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
     
    int n;Fio::Get(n);
    register int i,j;for(i=1;i<=n;++i)Fio::Get(seq[i]);
    Build(1,n,ScapeTreeRoot);
 
    int Q;Fio::Get(Q);
    char qte;int x,y,z,lans=0;
    while(Q--){
        qte=Fio::Getch();
        if(qte=='Q'){
            Fio::Get(x),Fio::Get(y),Fio::Get(z);
            Fio::Print(lans=GlobalQuery(x^lans,y^lans,z^lans));
        }
        if(qte=='M'){
            Fio::Get(x),Fio::Get(y);
            ScapeModify(ScapeTreeRoot,x^lans,AskScapeVal(ScapeTreeRoot,x^lans),y^lans);
        }
        if(qte=='I'){
            Fio::Get(x),Fio::Get(y);
            GlobalInsertValue(x^lans,y^lans);
        }
    }
 
    return Fio::Final(),0;
}