题面

传送门

思路

发现强制在线了......

本来可以树套树解决的问题，现在外层不能使用线段树了，拿什么替代呢？

我们需要一种支持单点插入、下套数据结构、数据结构上传合并复杂度最多单log，不能旋转的数据结构

这不是摆明了用重量平衡树吗？

我选了替罪羊树作为上层结构，下面套了一棵线段树，就做完了

查询的时候把替罪羊树上对应的log个区间提取出来，一起在底层权值线段树上二分即可

详见代码注释

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cassert>

#include<queue>

using namespace std;

inline int read(){

    int re=0,flag=1;char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-') flag=-1;

        ch=getchar();

    }

    while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

    return re*flag;

}

int s[20000010],ls=0,rs=0;

namespace ctrl{//内存分配器

    int cnt=0;

    int get(){

        int re;

        if(ls^rs){

            re=s[ls];

            ls++;if(ls==20000000) ls=0;

        }

        else re=(++cnt);

        return re;

    }

    void rec(int x){

        s[rs++]=x;

        if(rs==20000000) rs=0;

    }

}

vector<int>st;

namespace seg{

    int ch[20000010][2],sum[20000010];

    void insert(int &cur,int l,int r,int pos,int val){//权值线段树修改

        if(!cur){

            cur=ctrl::get();

            ch[cur][0]=ch[cur][1]=0;

        }

        if(l==r){sum[cur]+=val;return;}

        int mid=(l+r)>>1;

        if(mid>=pos) insert(ch[cur][0],l,mid,pos,val);

        else insert(ch[cur][1],mid+1,r,pos,val);

        sum[cur]=sum[ch[cur][0]]+sum[ch[cur][1]];

    }

    vector<int>s,ss;

    int query(int l,int r,int k){

        if(l==r) return l;

        int mid=(l+r)>>1,re=0,i;

        for(i=0;i<s.size();i++){//多个对象同步查询，s是对应区间，ss是对应单点

            re+=sum[ch[s[i]][0]];

        }

        for(i=0;i<ss.size();i++){

            re+=(ss[i]>=l&&ss[i]<=mid);

        }

        if(re>=k){

            for(i=0;i<s.size();i++) s[i]=ch[s[i]][0];

            return query(l,mid,k);

        }

        else{

            for(i=0;i<s.size();i++) s[i]=ch[s[i]][1];

            return query(mid+1,r,k-re);

        }

    }

    void dump(int cur){//拍扁替罪羊的过程中回收线段树节点

        if(!cur) return;

        dump(ch[cur][0]);dump(ch[cur][1]);

        ch[cur][0]=ch[cur][1]=sum[cur]=0;ctrl::rec(cur);

    }

}

int root,unb;

double alpha=0.8;

namespace scp{//替罪羊

    int ch[150010][2],siz[150010],rt[150010],v[150010],cnt;

    void update(int cur){

        siz[cur]=siz[ch[cur][0]]+siz[ch[cur][1]]+1;

    }

    void dfs(int u){//拍扁

        if(!u) return;

        seg::dump(rt[u]);

        dfs(ch[u][0]);

        st.push_back(u);

        dfs(ch[u][1]);

    }

    void build(int l,int r,int &cur){

        if(l>r) return;

        int mid=(l+r)>>1;

        cur=st[mid];

        ch[cur][0]=ch[cur][1]=0;siz[cur]=1;rt[cur]=0;

        build(l,mid-1,ch[cur][0]);build(mid+1,r,ch[cur][1]);

        update(cur);

        for(int i=l;i<=r;i++)

            seg::insert(rt[cur],0,70000,v[st[i]],1);

    }

    void rebuild(int &cur){//替罪羊重构

        st.clear();dfs(cur);

        build(0,st.size()-1,cur);

    }

    void insert(int &cur,int rk,int val){//替罪羊插入、判断重构

        if(!cur){

            cur=++cnt;

            ch[cur][0]=ch[cur][1]=0;siz[cur]=1;v[cur]=val;rt[cur]=0;

            seg::insert(rt[cur],0,70000,val,1);return;

        }

        seg::insert(rt[cur],0,70000,val,1);

        int L=siz[ch[cur][0]];

        if(L>=rk) insert(ch[cur][0],rk,val);

        else insert(ch[cur][1],rk-L-1,val);

        update(cur);

        if((double)(siz[cur])*alpha>(double)(max(siz[ch[cur][0]],siz[ch[cur][1]]))){

            if(unb){

                if(ch[cur][0]==unb) rebuild(ch[cur][0]);

                else rebuild(ch[cur][1]);

                unb=0;

            }

        }

        else unb=cur;

    }

    int ori;

    void change(int cur,int rk,int val){//替罪羊区间修改

        seg::insert(rt[cur],0,70000,val,1);

        if(siz[ch[cur][0]]+1==rk){ori=v[cur];v[cur]=val;}

        else if(siz[ch[cur][0]]>=rk) change(ch[cur][0],rk,val);

        else change(ch[cur][1],rk-siz[ch[cur][0]]-1,val);

        seg::insert(rt[cur],0,70000,ori,-1);

    }

    void query(int cur,int l,int r){//替罪羊上提取查询区间，如果区间覆盖了当前点，就把当前点加入查询序列

        assert(cur);

        if(l==1&&r==siz[cur]){

            seg::s.push_back(rt[cur]);return;

        }

        if(siz[ch[cur][0]]+1>=l&&siz[ch[cur][0]]+1<=r) seg::ss.push_back(v[cur]);

        if(r<=siz[ch[cur][0]]) query(ch[cur][0],l,r);

        else if(l>siz[ch[cur][0]]+1) query(ch[cur][1],l-siz[ch[cur][0]]-1,r-siz[ch[cur][0]]-1);

        else{

            if(l<=siz[ch[cur][0]]) query(ch[cur][0],l,siz[ch[cur][0]]);

            if(r>siz[ch[cur][0]]+1) query(ch[cur][1],1,r-siz[ch[cur][0]]-1);

        }

    }

}

int n,Q;

int main(){

    n=read();int i,t1,t2,t3;char ss[10];int lastans=0;

    for(i=1;i<=n;i++){

        t1=read();

        scp::insert(root,i,t1);

        if(unb){

            unb=0;

            scp::rebuild(root);

        }

    }

    Q=read();

    while(Q--){

        scanf("%s",ss);

        if(ss[0]=='Q'){

            t1=read();t2=read();t3=read();

            t1^=lastans;t2^=lastans;t3^=lastans;

            seg::s.clear();seg::ss.clear();

            scp::query(root,t1,t2);

            printf("%d\n",lastans=seg::query(0,70000,t3));

        }

        if(ss[0]=='M'){

            t1=read();t2=read();

            t1^=lastans;t2^=lastans;

            scp::change(root,t1,t2);

        }

        if(ss[0]=='I'){

            t1=read();t2=read();unb=0;

            t1^=lastans;t2^=lastans;

            scp::insert(root,t1-1,t2);

            if(unb){

                unb=0;

                scp::rebuild(root);

            }

        }

    }

}

巴特西

[bzoj3065] 带插入区间第k小值 [重量平衡树套线段树]

题面

思路

Code

最新文章

热门文章