题解 P2787 【语文1（chin1）- 理理思维】（分块）

· · 题解

这是一个有确定复杂度上限的暴力解法——分块

虽然题解区已经有分块了，但是ta并没有对lazy数组运用到极致，还疯狂maintain，导致时间复杂度极高，需要开O2，于是我稍微魔改了一番，锤了一些珂朵莉树达到了最优解第二页。

思路：

操作1：被分块艹烂了的操作，暴力扫整块和散块\sqrt{n}的时间内可以完成。

操作2：运用lazy数组，把整块的字母标记，需要时下传（maintain）到整个块，暴力修改散块，同样是\sqrt{n}的。

操作3：暴力快排？？成功爆炸，但是我们仔细一想，因为值域是1～26，所以桶排是一个非常好的选择，那么我们可以统计区间中每一个字母出现的次数，按顺序插入即可。时间复杂度。。。大体上还是\sqrt{n}吧，然而查询插入都要26次，所以这个常数算起来。。。

为了不被ODT吊打，我们需要做一些优化：

减少maintain

如果当前块有懒标记，下传的代价就是\sqrt{n}的，非常慢，所以我们能不maintain就不maintain，首先修改和查询整块的时候就没必要了，直接修改懒标记和查询就行。总耗时：3700ms->2100ms->900ms（O2）

对操作三剪枝

显然，这个程序的复杂度基本取决于操作三的复杂度，所以优化操作三的复杂度性价比是很高的。我们发现，对于有懒标记的块，它只会对一个字母做贡献，不需要扫26次，于是我们加个特判，又减小了一半常数。总耗时：900ms->450ms，不开O2：1300ms

至此，其它的优化都是在O（n\sqrt{n})的复杂度上小修小补，优化空间不大，等蒟蒻我有时间了再来尝试吧。

代码&注释：

#include<bits/stdc++.h>
using namespace std;
#define Re register 
#define MN 50005
int n,m,sum[225][26],T,loc[MN],len,opt,x,y,num[26];
char k[2],lazy[225],ch[MN];
//sum：每个块各个字母的数量    loc：表示某个位置在哪个块
//num：各个字母的数量（用于操作三）//lazy：懒标记
inline int read(){
    int a=0;
    char c=getchar();
    while(c>57||c<48)c=getchar();
    while(48<=c&&c<=57){
        a=a*10+c-48;
        c=getchar();
    }
    return a;
}
inline void maintain(int x){
    int pos=loc[x];
    if(lazy[pos]) {
        int l=(pos-1)*len+1,r=pos*len;
        for(int i=l;i<=r;++i) ch[i]=lazy[pos];
        for(int i=0;i<26;++i) sum[pos][i]=0;
        sum[pos][lazy[pos]-'A']=len;
        lazy[pos]=0;
    }
}//必要时下传
inline int ask(int x,int y,char k){
    if(y<x) return 0;
    int l=(x-1)/len+1+(x%len!=1),r=y/len,ans=0;
    if(l>r){
        maintain(x);maintain(y);//查询散块时下传
        for(int i=x;i<=y;++i)ans+=(ch[i]==k);
        return ans;
    }
    for(int i=l;i<=r;++i)
        ans+=lazy[i]?((k==lazy[i])*len):sum[i][k-'A'];
    int L=(l-1)*len,R=r*len+1;
    maintain(x);maintain(y);
    for(int i=x;i<=L;++i){ans+=(ch[i]==k);}
    for(int i=R;i<=y;++i){ans+=(ch[i]==k);}
    return ans;
}
void ASK(int x,int y){//查询26个字母
    if(y<x) return;
    int l=(x-1)/len+1+(x%len!=1),r=y/len;
    if(l>r){
        maintain(x);maintain(y);
        for(int i=x;i<=y;++i)++num[ch[i]-'A'];
        return;
    }
    for(int i=l;i<=r;++i){
        if(lazy[i])num[lazy[i]-'A']+=len;
        else for(int k=0;k<26;++k)
            num[k]+=sum[i][k];//小剪枝
    }
    int L=(l-1)*len,R=r*len+1;
    maintain(x);maintain(y);
    for(int i=x;i<=L;++i){++num[ch[i]-'A'];}
    for(int i=R;i<=y;++i){++num[ch[i]-'A'];}
    return;
}
inline void change(int x,int y,char k){
    if(y<x) return;
    int l=(x-1)/len+1+(x%len!=1),r=y/len;
    if(l>r){
        maintain(x);maintain(y);
        for(int i=x;i<=y;++i){
            --sum[loc[i]][ch[i]-'A'];
            ++sum[loc[i]][k-'A'];
            ch[i]=k;
        }
        return;
    }
    for(int i=l;i<=r;++i){lazy[i]=k;}//不需要maintain
    int L=(l-1)*len,R=r*len+1;
    maintain(x);maintain(y);//修改散块时maintain
    for(int i=x;i<=L;++i){
        --sum[l-1][ch[i]-'A'];
        ++sum[l-1][k-'A'];
        ch[i]=k;
    }
    for(int i=R;i<=y;++i){
          --sum[r+1][ch[i]-'A'];
          ++sum[r+1][k-'A'];
          ch[i]=k;
    }
}
int main(){
    scanf("%d%d%s",&n,&m,ch+1);
    for(int i=0;i<n;++i)if(ch[i]>'Z') ch[i]=(ch[i]-'a'+'A');
    T=sqrt(n);len=n/T;
    for(Re int i=1;i<=n;++i)loc[i]=(i-1)/len+1;
    for(Re int i=1;i<=T;++i){
        int l=(i-1)*len+1;int r=i*len;
        for(Re int j=l;j<=r;++j)
            ++sum[i][ch[j]-'A'];
    }
    for(Re int i=1;i<=m;++i){
        opt=read();x=read();y=read();
        if(opt==1){
            scanf("%s",k);
            if(k[0]>'Z') k[0]=(k[0]-'a'+'A');
            printf("%d\n",ask(x,y,k[0]));
        }
        else if(opt==2){
            scanf("%s",k);
            if(k[0]>'Z') k[0]=(k[0]-'a'+'A');
            change(x,y,k[0]);
        }
        else {
            ASK(x,y);
            for(Re int j=0;j<26;++j){
                change(x,x+num[j]-1,char(j+'A'));
                x+=num[j];
                num[j]=0;
            }
        }
    }
    return 0;
}

总结

这题打了我5h+，主要还是不太熟练分块的左右边界条件和注意事项吧，调分块题有个比较好用的小技巧：用同样的数据，更改块的大小，可以很方便地检查边界是否打挂。