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

· · 题解

块状链表。

为了尽量好理解，我会一个问题一个问题来讲。

前置知识

一、如何求第 k 小？

值域分块。

对于每个块，记录两个东西：

  1. 值为 x 的数的个数的前缀和。
  2. 值属于第 k 块的数的个数的前缀和。

代码：

struct Block {
    int l,r,size;
    int sk[305];//块内有几个属于这一块 的前缀和
    int s[70005];//块内有几个等于x 的前缀和
    int a[605];
    int& operator [](const int k) {
        return a[k];
    }
} b[605];

有了这些东西，怎么求区间第 k 小？

先要找到 l,r 在哪个块。代码如下：

    int now=L,lbel,rbel;
    while(b[now].size<l)l-=b[now].size,now=b[now].r;
    lbel=now,now=L;
    while(b[now].size<r)r-=b[now].size,now=b[now].r;
    rbel=now;

若 l,r 在同一个块内，只需扫一遍，将值为 x 的数的个数和值在某一块内的数的个数统计出来。

然后，先从小到大枚举块，边做前缀和。找到答案在哪一块后，从小到大枚举，找到答案的具体位置。

代码如下（注意清空临时数组）：

    if(lbel==rbel) {
        for(int i=l; i<=r; i++)tmps[b[lbel][i]]++,tmpsk[bel[b[lbel][i]]]++;
        now=1;
        while(tmpsk[now]<k)k-=tmpsk[now],now++;
        now=(now-1)*THREEHUNDRED;
        while(tmps[now]<k)k-=tmps[now],now++;
        for(int i=l; i<=r; i++)tmps[b[lbel][i]]--,tmpsk[bel[b[lbel][i]]]--;
        return now;
    }

若 l,r 不在同一个块内，先同样地将两边零散的个数统计出来。然后从小到大枚举答案所在的值域块，用总个数前缀和。找到答案在哪一块后，从小到大枚举，同样地做前缀和。

对于每一个数，它的出现次数等于：s_{r\text{的左边}}-s_l+\text{两边零散的}

代码如下：

    for(int i=l; i<=b[lbel].size; i++)tmps[b[lbel][i]]++,tmpsk[bel[b[lbel][i]]]++;
    for(int i=1; i<=r; i++)tmps[b[rbel][i]]++,tmpsk[bel[b[rbel][i]]]++;
    now=1;
    while(tmpsk[now]+b[b[rbel].l].sk[now]-b[lbel].sk[now]<k)k-=tmpsk[now]+b[b[rbel].l].sk[now]-b[lbel].sk[now],now++;
    now=(now-1)*THREEHUNDRED;
    while(tmps[now]+b[b[rbel].l].s[now]-b[lbel].s[now]<k)k-=tmps[now]+b[b[rbel].l].s[now]-b[lbel].s[now],now++;
    for(int i=l; i<=b[lbel].size; i++)tmps[b[lbel][i]]--,tmpsk[bel[b[lbel][i]]]--;
    for(int i=1; i<=r; i++)tmps[b[rbel][i]]--,tmpsk[bel[b[rbel][i]]]--;
    return now;

你已经渡过了最难的一关，接下来的都很简单了。

二、如何修改？

首先找到这个数所在的块。从这个块往后跳，将他原来的值的的个数减一，新值的个数加一，同时维护值域分块。代码如下：

    int now=L;
    while(b[now].size<x)x-=b[now].size,now=b[now].r;
    int before=b[now][x],after=k;
    if(before==after)return ;
    b[now][x]=after;
    while(now) {
        b[now].sk[bel[before]]--;
        b[now].sk[bel[after]]++;
        b[now].s[before]--;
        b[now].s[after]++;
        now=b[now].r;
    }

三、如何插入？

直接暴力插入，将他之后的所有元素后移，同时按照（二）中的方法维护前缀和。

但是，假如一直往同一个块里插东西，显然时间爆炸。

因此，当块的大小大于一个阈值的时候，我们就将其分裂成两个小块。方便起见，我们看成把原块的后一半分出去。

显然分裂不会对后面的块的前缀和产生影响，我们只需要考虑维护这两个小块。

后面的小块的所有信息其实和原来的是一样的，复制过去就行。

维护原来的块，只需要扫一遍后面的块，把后面的块中的元素减掉就行了。

然后同时维护一下链表，把分裂前后面那个块接到分出的块上就好了。

代码如下：

void Split(int now) {
    int newb=++S;
    b[newb].r=b[now].r,b[b[now].r].l=newb,b[now].r=newb,b[newb].l=now;
    //cout<<"Splitting:"<<now<<' '<<newb<<endl;
    //cout<<b[now].l<<' '<<b[now].r<<' '<<b[newb].l<<' '<<b[newb].r<<endl;
    b[newb].size=b[now].size/2;
    int tmp=b[now].size-b[newb].size;
    memcpy(b[newb].sk,b[now].sk,sizeof(b[now].sk));
    memcpy(b[newb].s,b[now].s,sizeof(b[now].s));
    for(int i=tmp+1; i<=b[now].size; i++) {
        b[newb][i-tmp]=b[now][i];
        b[now].sk[bel[b[now][i]]]--,b[now].s[b[now][i]]--;
        b[now][i]=0;
    }
    b[now].size=tmp;
}
void Insert(int x,int k) {
    //cout<<"RealInsert:"<<x<<' '<<k<<endl;
    int now=L;
    while(b[now].size<x){
        if(b[now].r)x-=b[now].size,now=b[now].r;
        else break;
    }
    for(int i=b[now].size; i>=x; i--)b[now][i+1]=b[now][i];
    b[now][x]=k,b[now].size++;
    int tn=now;
    while(now) {
        b[now].sk[bel[k]]++;
        b[now].s[k]++;
        now=b[now].r;
    }
    if(b[tn].size>THREEHUNDRED*2)Split(tn);
}

四、结语

相信看到这里，你已经有能力自己写出代码了。

其实这题并不难，只要你想好了写，并且有一段充足的时间（我用了 2.5h）调试，应该是能够将其 AC 的。

这种值域分块的想法，其实在其他题中也可以借鉴。

完结撒花~~