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

· · 题解

我是来给daniel14311531大佬的n\sqrt n方法做注解的。

1.分块怎么高效求第K大。 首先网上那些二分套主席树套分块之类的都不在我们的讨论范围，一点也不优美。

下面介绍一个大杀器，时代的新（对博主来说是新）科技：

值域分块。

就是对查询的值域进行分块。

具体来说就是设两个数组S1[]和S2[]

S1[i] = 值在[i*S,i*S+S-1]间的数的数量。

S2[i] = 值为i的数的数量。

那么求第K大就可以从小到大枚举块，求出第K大在值域中的哪一块。

然后再在那一块中枚举权值。

两步都是O(\sqrt n)的。

那么如果跨越多块，我们就需要做到O(1)求出一个区间内所有块的S1,S2

可以前缀和。 恰好 。。。。。这个S1,S2的修改是O(1)的，那么修改前缀和就是O(\sqrt n)的， 所以总复杂度还是O(\sqrt n)的！ 不完整的块把他们的S1,S2暴力求出即可。

2.如何在有插入的情况下维护分块。

块状链表。

就是不把块放在序列上。

前一块和后一块互相连接像链表一样。

块中是一个数组。

有O(\sqrt n)个块，块大小为O(\sqrt n)。

那么我们相当于是把对于插入-查询操作O(1)-O(n)的链表和O(n)-O(1)的数组按照一块一块交错实现，得到了一个对于插入-查询操作O(1)+O(\sqrt n)-O(\sqrt n)+O(1)的数据结构-块状链表。 其实链表套链表也是O(\sqrt n) - O(\sqrt n)的。。。。。。但是实现时会引起不适。 分块的所有操作都可以用块状链表实现，实现方法类似。 上面的值域分块同理。

真的比O(n\log ^2n)快好多。。。。。。。 AC Code:

#include<bits/stdc++.h>
#define maxn 70005
#define S 310
using namespace std;

char cb[1<<17],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<17,stdin),cs==ct)?0:*cs++)
inline void read(int &res){
    char ch;
    for(;!isdigit(ch=getc()););// if(ch=='-') f=1;
    for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
    //(f) && (res=-res);
}

int n;

struct block{
    int lb,rb;
    int a[S*2+10],cntS[maxn/S+5],cnt[maxn],siz;
}B[maxn/S],Nb;
int flb = 1 , cnt_bl = 0 , Mx = 0;
int id[maxn];

int Query(int x,int y,int k){
    int lb=1,rb=1,ret=0;
    for(;B[lb].siz && B[lb].siz<x;x-=B[lb].siz,lb=B[lb].rb);
    for(;B[rb].siz && B[rb].siz<y;y-=B[rb].siz,rb=B[rb].rb);
    //printf("%d %d %d\n",lb,rb,B[1].siz);
    if(lb == rb){
        //printf("%d %d\n",x,y);
        for(int i=x-1,j=y-1,tmp;i<=j;i++){
            //printf("%d\n",id[B[lb].a[i]]);
            tmp = B[lb].a[i];
            Nb.cntS[id[tmp]]++,
            Nb.cnt[tmp]++;
        }
        for(int i=1;i<=id[maxn-1];i++){
            //printf("%d %d\n",Nb.cntS[i],k);
            if(Nb.cntS[i]>=k){
                for(int j=(i-1)*S;;j++){
                    //printf("%d %d\n",j,k);
                    if(k<=Nb.cnt[j]){ ret=j;break; }
                    else k-=Nb.cnt[j];
                }
                break;
            }
            else k-=Nb.cntS[i];
        }
        for(int i=x-1,j=y-1,tmp;i<=j;i++){
            //printf("%d\n",id[B[lb].a[i]]);
            tmp = B[lb].a[i];
            Nb.cntS[id[tmp]]--,
            Nb.cnt[tmp]--;
        }
        return ret;
    }
    for(int i=x-1,tmp;i<B[lb].siz;i++){
        tmp = B[lb].a[i],
        Nb.cntS[id[tmp]]++,
        Nb.cnt[tmp]++;
    }
    for(int i=0,tmp;i<y;i++){
        tmp = B[rb].a[i],
        Nb.cntS[id[tmp]]++,
        Nb.cnt[tmp]++;
    }
    rb=B[rb].lb;
    for(int i=1,tmp;i<=id[Mx];i++){
        tmp = Nb.cntS[i]+B[rb].cntS[i]-B[lb].cntS[i];
        if(tmp>=k){
            for(int j=(i-1)*S,res;;j++){
                res = Nb.cnt[j]+B[rb].cnt[j]-B[lb].cnt[j];
                if(k<=res){ ret=j;break; }
                else k-=res;
            }
            break;
        }
        else k-=tmp;
    }
    rb=B[rb].rb;
    for(int i=x-1,tmp;i<B[lb].siz;i++){
        tmp = B[lb].a[i],
        Nb.cntS[id[tmp]]--,
        Nb.cnt[tmp]--;
    }
    for(int i=0,tmp;i<y;i++){
        tmp = B[rb].a[i],
        Nb.cntS[id[tmp]]--,
        Nb.cnt[tmp]--;
    }
    return ret;
}

void Modify(int x,int y){
    int lb=1;
    for(;B[lb].siz && B[lb].siz<x;x-=B[lb].siz,lb=B[lb].rb);
    int py = B[lb].a[x-1]; B[lb].a[x-1] = y;
    for(;lb;lb=B[lb].rb)
        B[lb].cntS[id[py]]--,
        B[lb].cntS[id[y]]++,
        B[lb].cnt[py]--,
        B[lb].cnt[y]++;
}

void split(int x){
    B[++cnt_bl].lb=x,B[cnt_bl].rb=B[x].rb;
    B[B[x].rb].lb=cnt_bl,B[x].rb=cnt_bl;
    B[cnt_bl].siz = S , B[x].siz -= S;
    memcpy(B[cnt_bl].a,B[x].a+B[x].siz,S*sizeof(int));
    memcpy(B[cnt_bl].cntS,B[x].cntS,sizeof B[x].cntS);
    memcpy(B[cnt_bl].cnt,B[x].cnt,sizeof B[x].cnt);
    for(int i=0;i<S;i++) 
        B[x].cntS[id[B[cnt_bl].a[i]]]--,
        B[x].cnt[B[cnt_bl].a[i]]--;
}

void Insert(int x,int y){
    int lb=1;x--;
    for(;B[lb].siz && B[lb].siz<x;x-=B[lb].siz,lb=B[lb].rb);
    for(int i=B[lb].siz++;i>x;i--) B[lb].a[i] = B[lb].a[i-1];
    B[lb].a[x]=y;
    for(int i=lb;i;i=B[i].rb)
        B[i].cntS[id[y]]++,
        B[i].cnt[y]++;
    if(B[lb].siz>=2*S) 
        split(lb);
}

int main(){
    //int t1 = clock();
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    read(n);
    for(int i=0;i<maxn;i++) id[i]=i/S+1;
    cnt_bl=id[n-1];
    for(int i=0;i<n;i++){
        int u = id[i] , x;
        read(x);
        B[u].a[B[u].siz++] = x;
        B[u].cntS[id[x]]++;
        B[u].cnt[x]++;
        Mx = max(Mx , x);
    }
    for(int i=2;i<=cnt_bl;i++)
    {
        B[i-1].rb=i,B[i].lb=i-1;
        for(int j=0;j<=Mx;j++){
            B[i].cnt[j] += B[i-1].cnt[j];
            if(j==0 || id[j]!=id[j-1]) 
                B[i].cntS[id[j]] += B[i-1].cntS[id[j]];
        }
    }
    int q;
    read(q);
    char s[2];
    for(int x,y,k,la=0;q--;){
        while(!isalpha(s[0]=getc()));
        //puts(s);
        //printf("@@@@%d\n",allsiz);
        if(s[0] == 'Q'){
            read(x),read(y),read(k);
            x ^= la , y ^= la , k ^= la;
            //printf("@@%d %d %d\n",x,y,k);
            printf("%d\n",la=Query(x,y,k));
        }
        else if(s[0] == 'M'){
            read(x),read(y);
            x ^= la , y ^= la;
            Mx = max(Mx ,y);
            //printf("$$%d %d\n",x,y);
            Modify(x,y);
        }
        else {
            read(x),read(y);
            x^=la , y ^= la;
            Mx = max(Mx , y);
            //printf("##%d %d\n",x,y);
            Insert(x,y);
        }
        //puts(s);
        //printf("%d\n",B[1].siz);
    }
    //freopen("CON","w",stdout);
    //printf("%d\n",clock()-t1);
}