题解 P4278 【带插入区间K小值】

· · 题解

题意：题如其名，带插入区间K小值。强制在线。

原题

这道题按道理来说是可以用奇妙的树套树两个log做过去的，但是由于题目右上角的那位毒瘤，被卡掉了。

那么能过的方法，就只有块状链表+值域分块了。

首先来介绍一下值域分块：

先看看怎么维护一个数列（不是区间）的静态K小值：

将值域(默认与 n 同阶)分成\sqrt{n}块，第 i 块表示第 i 个范围为\sqrt{n}的值域。

弄两个数组，一个Size，一个Alive。Size(i)表示第 i 块值域内出现了几个数，Alive(i)表示 i 这个数在数列中共出现过几次。这两个数组可以轻松 O(n) 建出。

然后对于整个K小值，我们可以遍历每一块值域，比较K与当前块内数的个数(Size)的大小。若K大，将K减去当前块内个数，遍历下一块；否则说明K小值就在这一块里了。 那么就可以利用Alive数组，遍历该块内所有值直到找到K小值。复杂度显然为O(\sqrt{n})。

再来看看区间静态K小值：

仍然是值域分块，不过这次利用前缀和的思想。把序列也分成\sqrt{n}块， 将Size,Alive改成二维：Size(i)(j)表示序列前 i 块中，值域第 j 块内出现过几个数；Alive(i)(j)表示序列前 i 块中，j 这个数出现过几次。这两个数组能O(n \sqrt{n}) 得到。

在弄两个一维数组s,cnt ，其用处大体与Size,Alive相同。具体见下文。

对于询问l,r,k ，l属于第 idl 块，r属于第 idr 块

若idl=idr，暴力从 l 扫到 r，把扫到的数拿去更新s,cnt。然后，用之前提到的做法O(\sqrt{n})得到答案。

否则，先暴力处理散块，更新s,cnt。然后，对于中间的块，我们可以利用

复杂度仍为$O(\sqrt{n})$。 在每次询问后，要把加进$s,cnt$里面的数从$s,cnt$里面扔掉，准备迎接下一次询问。 接下来考虑修改（单点）： 既然只要改一个值，那改掉其所在序列块及其以后所有块的$Size,Alive$即可。一次修改显然$O(1)$，由于序列块有$O(\sqrt{n})$ 块，单次修改复杂度仍为 $O(\sqrt{n})$，且几乎与静态代码量没有区别。 对比主席树，如果主席树要带修，那真是伤筋动骨的，对比值域分块也不再有多少优势。果然啊，越暴力的算法能维护的东西越多。 接下来，就是最后一关。插入： 介绍一下我们今天的第二位主角：块状链表。简单的说，就是序列块与序列块之间**以链表的形式相连**，**每个块内部维护其范围内的数列**。 那么插入的时候，就可以愉快的直接将对应序列块中该向后移的部分后移，复杂度为块长。之后再将$Size,Alive$中要增加的部分加上去，复杂度为块的数量。 问题来了，要是我们不断往同一个块里面插入呢？这个块岂不是会越来越长，最后导致复杂度倒退成$O(n)$? 这就是我们要把普通的分块改成块状链表的原因。当我们发现一个块长度变成 $2\sqrt{n}$的时候，我们直接把它弄成两半，每一份长为$\sqrt{n}$。 也就是把原来的块的后半部分撕下来，扔到一个新块上，且这个新块要变成在原来的块后面的第一个块。 考虑如何实现：把原块后半部分交给一个新块容易，毕竟数据量也就$O(\sqrt{n})$，且由于数据本身没有变化，不用去修改其他块，能够轻松$O(\sqrt{n})$ 解决。 而我们发现，要新开一个块，且该块要变成要求的块后面的第一个块，这个操作能够用**链表**相当容易的解决。于是，就有了块状链表。 复杂度，仍是铁打不动的$O(\sqrt{n})$ 。 $\texttt{Talk is cheap,show me your code.} 
#include <cstdio>

const int maxn=1e5+5,maxl=300;int maxx;

struct IO{
    IO(){};char c;
    inline char gc(){
        static char buf[maxn],*p1=buf,*p2=buf;
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)?EOF:*p1++;
    }
    inline IO&operator>>(int &_){
        _=0;bool f=1;c=gc();while(c<'0'||c>'9'){if(c=='-') f=0; c=gc();}
        while(c>='0'&&c<='9'){_=_*10+c-48;c=gc();}if(!f) _=-_;return *this;
    }
    inline IO&operator<<(int x){
        if(!x){putchar(48);putchar('\n');return *this;}
        static int wt[40],len;len=0;if(x<0){putchar('-');x=-x;}
        for(;x;x/=10){wt[++len]=x%10;}
        while(len){putchar(wt[len--]+48);}
        putchar('\n');return *this;
    }
}io;

int n,m,block_size,last_ans;
int Size[maxl*3][maxl+5],Alive[maxl*3][maxn+5],pre_len[maxn],bl[maxn];//bl用来管下标的所属块，pre_len[i]表示c[i]前有几个数
int s[maxl+5],cnt[maxn];

inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}

inline int L(int id){return (id-1)*maxl+1;}
inline int R(int id){return min(id*maxl,maxx);}//这个用来管值域的分块情况
inline int where(int val){return (val-1)/maxl+1;}//值域所属块

struct Block{
    int size[maxl+5],alive[maxn];
    int a[(maxl<<1)+5],len;int lb,rb;
    inline void ins(int val){size[where(val)]++,alive[val]++;}
    inline void del(int val){size[where(val)]--,alive[val]--;}
    inline void insert(int pos,int val){
        len++;for(int i=len;i>=pos+2;i--) a[i]=a[i-1];
        a[pos+1]=val;//将val插到pos后面
    }
    inline void push_back(int val){a[++len]=val;}
    int& operator[](int id){
        return a[id];//这样会很舒爽
    }
}c[maxl];int block_len=0;

inline void modify(int pos,int val){
    int id=bl[pos],_=pos-pre_len[id];int old=c[id][_];
    c[id].del(old),c[id].ins(val);c[id][_]=val;
    for(int i=id;i;i=c[i].rb){
        Size[i][where(old)]--;Alive[i][val]++;
        Alive[i][old]--;Size[i][where(val)]++;
    }
}

inline void ins(int val){s[where(val)]++,cnt[val]++;}
inline void del(int val){s[where(val)]--,cnt[val]--;}

inline int query(int key){
    for(int i=1;i<=where(maxx);i++){
        if(key<=s[i]){
            for(int j=L(i);j<=R(i);j++){
                if(key<=cnt[j]) return j;
                key-=cnt[j];
            }
        }
        else key-=s[i];
    }//值域分块的玄妙操作
    return 0;
}

inline int Query(int l,int r,int key){
    int idl=bl[l],idr=bl[r];
    if(idl==idr){
        for(int i=l;i<=r;i++) ins(c[idl][i-pre_len[idl]]);
        int res=query(key);
        for(int i=l;i<=r;i++) del(c[idl][i-pre_len[idl]]);
        return res;
    }
    for(int i=l;i<=pre_len[c[idl].rb];i++) ins(c[idl][i-pre_len[idl]]);
    for(int i=pre_len[idr]+1;i<=r;i++) ins(c[idr][i-pre_len[idr]]);
    int res=0;
    for(int i=1;i<=where(maxx);i++){
        int now=s[i]+Size[c[idr].lb][i]-Size[idl][i];
        if(key<=now){
            for(int j=L(i);;j++){
                int _=cnt[j]+Alive[c[idr].lb][j]-Alive[idl][j];
                if(key<=_){res=j;break;}
                else key-=_;
            }break;
        }else key-=now;
    }//值域分块，多么美妙
    for(int i=l;i<=pre_len[c[idl].rb];i++) del(c[idl][i-pre_len[idl]]);
    for(int i=pre_len[idr]+1;i<=r;i++) del(c[idr][i-pre_len[idr]]);
    return res;
}

void split(int id){//把第id块拆了
    c[++block_len].lb=id;c[block_len].rb=c[id].rb;c[c[id].rb].lb=block_len;c[id].rb=block_len;
    int now=block_size+1;for(;now<=c[id].len;now++){c[block_len].push_back(c[id][now]),c[block_len].ins(c[id][now]),c[id].del(c[id][now]);}
    pre_len[block_len]=pre_len[id]+(c[id].len=block_size);
    for(int i=pre_len[block_len]+1;i<=pre_len[block_len]+c[block_len].len;i++) bl[i]=block_len;
    for(int i=1;i<=where(maxx);i++) Size[block_len][i]=(Size[id][i]=Size[c[id].lb][i]+c[id].size[i])+c[block_len].size[i];
    for(int i=1;i<=maxx;i++) Alive[block_len][i]=(Alive[id][i]=Alive[c[id].lb][i]+c[id].alive[i])+c[block_len].alive[i];
}

void insert(int pos,int val){
    int id=bl[pos];int _=pos-pre_len[id];
    c[id].insert(_,val);for(int i=c[id].rb;i;i=c[i].rb) pre_len[i]++;c[id].ins(val);
    for(int i=id;i;i=c[i].rb){
        Size[i][where(val)]++,Alive[i][val]++;
        bl[pre_len[i]+c[i].len]=i;bl[pre_len[i]+1]=i;
    }
    if(c[id].len>=block_size*2) split(id);//要是发现它不对劲
}

void build(){
    block_size=maxl;for(int i=1;i<=n;i++) bl[i]=(i-1)/block_size+1;
    block_len=bl[n];bl[0]=1;//我的代码中要是被要求把一个数插到第一个数，他会去找第零个数在哪块里面
    for(int i=1;i<=block_len;i++){
        c[i].lb=i-1,c[i].rb=i+1;
    }
    c[block_len].rb=0;
    for(int i=1;i<=n;i++){
        int x;io>>x;maxx=max(maxx,++x);//因为我讨厌0，所以所有出现的价值都被我加1了
        c[bl[i]].push_back(x);c[bl[i]].ins(x);
    }
    for(int i=1;i<=block_len;i++){
        pre_len[i]=pre_len[i-1]+c[i-1].len;
        for(int j=1;j<=where(maxx);j++) Size[i][j]=Size[i-1][j]+c[i].size[j];
        for(int j=1;j<=maxx;j++) Alive[i][j]=Alive[i-1][j]+c[i].alive[j];
    }
}

int main(){
    io>>n;build();io>>m;
    for(int i=1;i<=m;i++){
        char opt=io.gc();while(opt>'Z'||opt<'A') opt=io.gc();
        if(opt=='M'){
            int pos,val;io>>pos>>val;pos^=last_ans,val^=last_ans;maxx=max(maxx,val+1);
            modify(pos,val+1);
        }
        if(opt=='Q'){
            int l,r,k;io>>l>>r>>k;l^=last_ans,r^=last_ans,k^=last_ans;
            io<<(last_ans=Query(l,r,k)-1);//由于我把所有出现元素+1，这里要-1
        }
        if(opt=='I'){
            int pos,val;io>>pos>>val;pos^=last_ans,val^=last_ans;maxx=max(maxx,val+1);
            insert(pos-1,val+1);//意思是把(val+1)塞到(pos-1)后面
        }
    }
    return 0;
}

当然，需要吸氧才能卡过时限。这里我选择维护每个点的所属块和每个块之前有几个数，你也可以选择不维护，要用的时候O(\sqrt{n})扫一遍，得到其所属块和块前有几个数。

你甚至可以在块内部维护一个链表。这个写法常数比起块内维护数组要大一些，不过亲测也能卡过去。