分块

Defy_HeavenS · 2025-09-07 11:38:17 · 算法·理论

题目

#6277. 数列分块入门 1 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。

技巧

区间加法需要一个标记 tag_i 表示块 i 被整体加了多少。散块暴力；整块用 tag。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n)，修改 \mathcal{O}(T+\frac{n}{T})，查询 \mathcal{O}(1)。最优块长为 \sqrt{n}。

代码

const int N=5e4+5,M=255;
int n,a[N],T,tot,be[M],en[M],bel[N],tag[M];

void init(){
    T=tot=sqrt(n);
    for(int i=1;i<=tot;i++){
        be[i]=en[i-1]+1,en[i]=i*T;
    }
    en[tot]=n;
    for(int i=1;i<=tot;i++){
        for(int j=be[i];j<=en[i];j++){
            bel[j]=i;
        }
    }
}
void update(int l,int r,int val){
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            a[i]+=val;
        }
        return;
    }
    for(int i=l;i<=en[bel[l]];i++){
        a[i]+=val;
    }
    for(int i=be[bel[r]];i<=r;i++){
        a[i]+=val;
    }
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        tag[i]+=val;
    }
}
int query(int pos){
    return a[pos]+tag[bel[pos]];
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    for(int i=1,op,l,r,c;i<=n;i++){
        cin>>op>>l>>r>>c;
        if(op){
            cout<<query(r)<<"\n";
        }else{
            update(l,r,c);
        }
    }
    return 0;
}

#6278. 数列分块入门 2 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。

技巧

由于小于某个值 x 的元素个数具有单调性，所以分完块后在块内排序。散块查询修改都直接暴力，但是修改后要重新排序；整块查询二分、修改用 tag。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n\log n)，修改 \mathcal{O}(T\log T+\frac{n}{T})，查询 \mathcal{O}(T+\frac{n}{T}\log T)。最优块长是 \sqrt{n}。

代码

const int N=5e4+5,M=255;
int n,T,tot,be[M],en[M],bel[N],tag[M];
PII a[N];

void init(){
    T=tot=sqrt(n);
    for(int i=1;i<=tot;i++){
        be[i]=en[i-1]+1,en[i]=i*T;
    }
    en[tot]=n;
    for(int i=1;i<=tot;i++){
        for(int j=be[i];j<=en[i];j++){
            bel[j]=i;
        }
        sort(a+be[i],a+en[i]+1);
    }
}
void update(int l,int r,int val){
    if(bel[l]==bel[r]){
        for(int i=be[bel[l]];i<=en[bel[r]];i++){
            if(l<=a[i].se&&a[i].se<=r) a[i].fi+=val;
        }
        sort(a+be[bel[l]],a+en[bel[r]]+1);
        return;
    }
    for(int i=be[bel[l]];i<=en[bel[l]];i++){
        if(l<=a[i].se&&a[i].se<=r) a[i].fi+=val;
    }
    sort(a+be[bel[l]],a+en[bel[l]]+1);
    for(int i=be[bel[r]];i<=en[bel[r]];i++){
        if(l<=a[i].se&&a[i].se<=r) a[i].fi+=val;
    }
    sort(a+be[bel[r]],a+en[bel[r]]+1);
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        tag[i]+=val;
    }
}
int query(int l,int r,int val){
    if(bel[l]==bel[r]){
        int res=0;
        for(int i=be[bel[l]];i<=en[bel[r]];i++){
            if(l<=a[i].se&&a[i].se<=r&&a[i].fi+tag[bel[i]]<val) res++;
        }
        return res;
    }
    int res=0;
    for(int i=be[bel[l]];i<=en[bel[l]];i++){
        if(l<=a[i].se&&a[i].se<=r&&a[i].fi+tag[bel[i]]<val) res++;
    }
    for(int i=be[bel[r]];i<=en[bel[r]];i++){
        if(l<=a[i].se&&a[i].se<=r&&a[i].fi+tag[bel[i]]<val) res++;
    }
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        int L=be[i],R=en[i],mid,ans=be[i]-1;
        while(L<=R){    //易错点，这里二分的lr不要与函数的lr搞混
            mid=L+R>>1;
            if(a[mid].fi+tag[bel[mid]]<val){
                ans=mid,L=mid+1;
            }else{
                R=mid-1;
            }
        }
        res+=ans-be[i]+1;
    }
    return res;
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].fi;
        a[i].se=i;
    }
    init();
    for(int i=1,op,l,r,c;i<=n;i++){
        cin>>op>>l>>r>>c;
        if(op){
            c*=c;
            cout<<query(l,r,c)<<"\n";
        }else{
            update(l,r,c);
        }
    }
    return 0;
}

#6279. 数列分块入门 3 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。

技巧

仍然是块内排序，同上一道题。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n\log n)，修改 \mathcal{O}(T\log T+\frac{n}{T})，查询 \mathcal{O}(T+\frac{n}{T}\log T)。最优块长是 \sqrt{n}。

这题出的不好，和上一题几乎一样，但作者是想让我们在块里维护 set。所以这题另外的技巧是可以在块里维护数据结构。

代码

const LL N=1e5+5,M=320,Inf=1e16+7;
LL n,T,tot,be[M],en[M],bel[N],tag[M];
PII a[N];

void init(){
    T=tot=sqrt(n);
    for(LL i=1;i<=tot;i++){
        be[i]=en[i-1]+1,en[i]=i*T;
    }
    en[tot]=n;
    for(LL i=1;i<=tot;i++){
        for(LL j=be[i];j<=en[i];j++){
            bel[j]=i;
        }
        sort(a+be[i],a+en[i]+1);
    }
}
void update(LL l,LL r,LL val){
    if(bel[l]==bel[r]){
        for(LL i=be[bel[l]];i<=en[bel[r]];i++){
            if(l<=a[i].se&&a[i].se<=r) a[i].fi+=val;
        }
        sort(a+be[bel[l]],a+en[bel[r]]+1);
        return;
    }
    for(LL i=be[bel[l]];i<=en[bel[l]];i++){
        if(l<=a[i].se&&a[i].se<=r) a[i].fi+=val;
    }
    sort(a+be[bel[l]],a+en[bel[l]]+1);
    for(LL i=be[bel[r]];i<=en[bel[r]];i++){
        if(l<=a[i].se&&a[i].se<=r) a[i].fi+=val;
    }
    sort(a+be[bel[r]],a+en[bel[r]]+1);
    for(LL i=bel[l]+1;i<=bel[r]-1;i++){
        tag[i]+=val;
    }
}
LL query(LL l,LL r,LL val){
    if(bel[l]==bel[r]){
        LL res=-Inf;
        for(LL i=be[bel[l]];i<=en[bel[r]];i++){
            if(l<=a[i].se&&a[i].se<=r&&a[i].fi+tag[bel[i]]<val) tmax(res,a[i].fi+tag[bel[i]]);
        }
        return res;
    }
    LL res=-Inf;
    for(LL i=be[bel[l]];i<=en[bel[l]];i++){
        if(l<=a[i].se&&a[i].se<=r&&a[i].fi+tag[bel[i]]<val) tmax(res,a[i].fi+tag[bel[i]]);
    }
    for(LL i=be[bel[r]];i<=en[bel[r]];i++){
        if(l<=a[i].se&&a[i].se<=r&&a[i].fi+tag[bel[i]]<val) tmax(res,a[i].fi+tag[bel[i]]);
    }
    for(LL i=bel[l]+1;i<=bel[r]-1;i++){
        LL L=be[i],R=en[i],mid,ans=-Inf;
        while(L<=R){
            mid=L+R>>1;
            if(a[mid].fi+tag[bel[mid]]<val){
                ans=a[mid].fi+tag[bel[mid]],L=mid+1;
            }else{
                R=mid-1;
            }
        }
        tmax(res,ans);
    }
    return res;
}

signed main(){
    cin>>n;
    for(LL i=1;i<=n;i++){
        cin>>a[i].fi;
        a[i].se=i;
    }
    init();
    for(LL i=1,op,l,r,c;i<=n;i++){
        cin>>op>>l>>r>>c;
        if(op){
            LL res=query(l,r,c);
            cout<<(res==-Inf?-1:res)<<"\n";
        }else{
            update(l,r,c);
        }
    }
    return 0;
}

#6280. 数列分块入门 4 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，区间求和。

技巧

区间求和需要一个块内和 sum_i 表示块 i 内数的和。散块暴力；整块修改用 tag、查询用 sum。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n)，修改 \mathcal{O}(T+\frac{n}{T})，查询 \mathcal{O}(T+\frac{n}{T})。最优块长为 \sqrt{n}。

代码

const int N=5e4+5,M=255;
int n,T,tot,be[M],en[M],bel[N];
LL a[N],sum[M],tag[M];

void init(){
    T=tot=sqrt(n);
    for(int i=1;i<=tot;i++){
        be[i]=en[i-1]+1,en[i]=i*T;
    }
    en[tot]=n;
    for(int i=1;i<=tot;i++){
        for(int j=be[i];j<=en[i];j++){
            bel[j]=i,sum[i]+=a[j];
        }
    }
}
void update(int l,int r,LL val){
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            a[i]+=val;
        }
        sum[bel[l]]+=(r-l+1)*val;
        return;
    }
    for(int i=l;i<=en[bel[l]];i++){
        a[i]+=val;
    }
    sum[bel[l]]+=(en[bel[l]]-l+1)*val;
    for(int i=be[bel[r]];i<=r;i++){
        a[i]+=val;
    }
    sum[bel[r]]+=(r-be[bel[r]]+1)*val;
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        tag[i]+=val,sum[i]+=(en[i]-be[i]+1)*val;
    }
}
LL query(int l,int r,int Mod){
    if(bel[l]==bel[r]){
        LL res=0;
        for(int i=l;i<=r;i++){
            (res+=a[i]+tag[bel[i]])%=Mod;
        }
        return res;
    }
    LL res=0;
    for(int i=l;i<=en[bel[l]];i++){
        (res+=a[i]+tag[bel[i]])%=Mod;
    }
    for(int i=be[bel[r]];i<=r;i++){
        (res+=a[i]+tag[bel[i]])%=Mod;
    }
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        (res+=sum[i])%=Mod;
    }
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    for(int i=1,op,l,r,c;i<=n;i++){
        cin>>op>>l>>r>>c;
        if(op){
            cout<<query(l,r,c+1)<<"\n";
        }else{
            update(l,r,c);
        }
    }
    return 0;
}

#6281. 数列分块入门 5 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间开方，区间求和。

技巧

由于开方操作只会减小不会增加，而且最多开方 \log \log V 次就一定固定在 0,1 两个数（这俩数开发后等于自己），不会再变化，本题中最多开方 6 次。所以记录块内非可以开发的数的个数（即非 0,1 数的个数），如果没有就直接跳过这个块。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n)，修改 \mathcal{O}(T+n) 但均摊是 \mathcal{O}(n)，查询 \mathcal{O}(T+\frac{n}{T})。最优块长为 \sqrt{n}。

代码

const int N=5e4+5,M=255;
int n,a[N],T,tot,be[M],en[M],bel[N],sum[M],can[M];

void init(){
    T=tot=sqrt(n);
    for(int i=1;i<=tot;i++){
        be[i]=en[i-1]+1,en[i]=i*T;
    }
    en[tot]=n;
    for(int i=1;i<=tot;i++){
        for(int j=be[i];j<=en[i];j++){
            bel[j]=i,sum[i]+=a[j],can[i]+=a[j]>1;
        }
    }
}
void update(int l,int r){
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            if(a[i]<=1) continue;
            sum[bel[i]]+=sqrt(a[i])-a[i];
            a[i]=sqrt(a[i]);
            if(a[i]<=1){
                can[bel[i]]--;
            }
        }
        return;
    }
    for(int i=l;i<=en[bel[l]];i++){
        if(a[i]<=1) continue;
        sum[bel[i]]+=sqrt(a[i])-a[i];
        a[i]=sqrt(a[i]);
        if(a[i]<=1){
            can[bel[i]]--;
        }
    }
    for(int i=be[bel[r]];i<=r;i++){
        if(a[i]<=1) continue;
        sum[bel[i]]+=sqrt(a[i])-a[i];
        a[i]=sqrt(a[i]);
        if(a[i]<=1){
            can[bel[i]]--;
        }
    }
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        if(!can[i]) continue;
        for(int j=be[i];j<=en[i];j++){
            if(a[j]<=1) continue;
            sum[i]+=sqrt(a[j])-a[j];
            a[j]=sqrt(a[j]);
            if(a[j]<=1){
                can[i]--;
            }
        }
    }
}
int query(int l,int r){
    if(bel[l]==bel[r]){
        LL res=0;
        for(int i=l;i<=r;i++){
            res+=a[i];
        }
        return res;
    }
    LL res=0;
    for(int i=l;i<=en[bel[l]];i++){
        res+=a[i];
    }
    for(int i=be[bel[r]];i<=r;i++){
        res+=a[i];
    }
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        res+=sum[i];
    }
    return res;
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    for(int i=1,op,l,r,c;i<=n;i++){
        cin>>op>>l>>r>>c;
        if(op){
            cout<<query(l,r)<<"\n";
        }else{
            update(l,r);
        }
    }
    return 0;
}

#6282. 数列分块入门 6 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及单点插入，单点询问，数据随机生成。Loj 上的数据最后三个点不是随机的。

技巧

与数列分块入门 3一样，技巧是可以在块里维护数据结构，这里维护 vector。每次先找到要插入或查询的块，插入就直接暴力插入，时间复杂度问题后面分析；查询也直接暴力找。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n)。因为随机，所以每个块被插入的元素个数在理论上相等。修改 \mathcal{O}(T+\frac{n}{T})，查询 \mathcal{O}(T+\frac{n}{T})。最优块长为 \sqrt{n}。

可是出题人跑数据跑了一辈子，跑出一个每次只加在第一个位置的数据……数据没有随机怎么办？需要引入一个操作：重新分块（重构），重构有很多种：

• 把整个序列重新分块（好写）；
  • 定期重构，一般是 \sqrt{m} 次插入后重构（这里的 m 是重构次数），如果 m 与 n 同阶那么复杂度不会受影响；
  • 有块超出范围后重构，范围一般是 2 到 5 倍的 \sqrt{n}。
• 把超出范围的块分成多份，一般为两份（难写）。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n)，修改 \mathcal{O}(T+\frac{n}{T})，查询 \mathcal{O}(T+\frac{n}{T})，重构 \mathcal{O}(n)，由于最多重构 \sqrt{n} 次，所以不影响复杂度。最优块长为 \sqrt{n}。

代码

const int N=1e5+5,B=605;
int n,m,a[N],T,tot;
vector<int>b[B],tmp;

void init(){
    T=sqrt(n),tot=n/T;
    if(n%T) tot++;
    for(int i=1,be,en=0;i<=tot;i++){
        be=en+1,en=i*T;
        if(i==tot) en=n;
        for(int j=be;j<=en;j++){
            b[i].pb(a[j]);
        }
    }
}
void rebuild(){
    tmp.clear();
    for(int i=1;i<=tot;i++){
        for(auto val:b[i]){
            tmp.pb(val);
        }
        b[i].clear();
    }
    T=sqrt(tmp.size()),tot=tmp.size()/T;
    if(tmp.size()%T) tot++;
    for(int i=1,be,en=0;i<=tot;i++){
        be=en+1,en=i*T;
        if(i==tot) en=tmp.size();
        for(int j=be;j<=en;j++){
            b[i].pb(tmp[j-1]);
        }
    }
}
void update(int pos,int val){
    for(int i=1,sum=0;i<=tot;i++){
        sum+=b[i].size();
        if(sum>=pos){
            sum-=b[i].size();
            int k=0;
            for(int j=0;j<b[i].size();j++){
                if(sum+j+1==pos){
                    k=j;
                    break;
                }
            }
            b[i].pb(val);
            for(int j=b[i].size()-2;j>=k;j--){
                swap(b[i][j],b[i][j+1]);
            }
            if(b[i].size()>=5*sqrt(m)){
                rebuild();
            }
            break;
        }
    }
}
int query(int pos){
    for(int i=1,sum=0;i<=tot;i++){
        sum+=b[i].size();
        if(sum>=pos){
            sum-=b[i].size();
            for(int j=0;j<b[i].size();j++){
                if(sum+j+1==pos){
                    return b[i][j];
                }
            }
        }
    }
}

signed main(){
    cin>>n;
    m=n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    for(int i=1,op,l,r,c;i<=n;i++){
        cin>>op>>l>>r>>c;
        if(op){
            cout<<query(r)<<"\n";
        }else{
            m++;
            update(l,r);
        }
    }
//  for(int i=1,j=1,op,l,r,c;i<=n;i++,j++){    //定期重构
//      cin>>op>>l>>r>>c;
//      if(op){
//          cout<<query(r)<<"\n";
//      }else{
//          m++;
//          update(l,r);
//      }
//      if((int)sqrt(n)==j){
//          rebuild();
//          j=0;
//      }
//  }
    return 0;
}

#6283. 数列分块入门 7 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间乘法，区间加法，单点询问。

技巧

需要两个标记 tag1,tag2，表示加法和乘法的标记，和线段树的标记合并一样，不多说了。这里要说的是散块的修改可能与标记冲突，所以要把标记打在要修改的散块，但时间复杂度不会受影响。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n)，修改 \mathcal{O}(T+\frac{n}{T})，查询 \mathcal{O}(1)。最优块长为 \sqrt{n}。

代码

const int N=1e5+5,M=320,Mod=10007;
int n,a[N],T,tot,be[M],en[M],bel[N],tag1[M],tag2[M];

void init(){
    T=tot=sqrt(n);
    for(int i=1;i<=tot;i++){
        be[i]=en[i-1]+1,en[i]=i*T;
    }
    en[tot]=n;
    for(int i=1;i<=tot;i++){
        tag2[i]=1;
        for(int j=be[i];j<=en[i];j++){
            bel[j]=i;
        }
    }
}
void pushdown(int bel){
    for(int i=be[bel];i<=en[bel];i++){
        a[i]=(a[i]*tag2[bel]+tag1[bel])%Mod;
    }
    tag1[bel]=0,tag2[bel]=1;
}
void update1(int l,int r,int val){
    if(bel[l]==bel[r]){
        pushdown(bel[l]);
        for(int i=l;i<=r;i++){
            (a[i]+=val)%=Mod;
        }
        return;
    }
    pushdown(bel[l]);
    for(int i=l;i<=en[bel[l]];i++){
        (a[i]+=val)%=Mod;
    }
    pushdown(bel[r]);
    for(int i=be[bel[r]];i<=r;i++){
        (a[i]+=val)%=Mod;
    }
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        (tag1[i]+=val)%=Mod;
    }
}
void update2(int l,int r,int val){
    if(bel[l]==bel[r]){
        pushdown(bel[l]);
        for(int i=l;i<=r;i++){
            (a[i]*=val)%=Mod;
        }
        return;
    }
    pushdown(bel[l]);
    for(int i=l;i<=en[bel[l]];i++){
        (a[i]*=val)%=Mod;
    }
    pushdown(bel[r]);
    for(int i=be[bel[r]];i<=r;i++){
        (a[i]*=val)%=Mod;
    }
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        (tag1[i]*=val)%=Mod,(tag2[i]*=val)%=Mod;
    }
}
int query(int pos){
    return (a[pos]*tag2[bel[pos]]+tag1[bel[pos]])%Mod;
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    for(int i=1,op,l,r,c;i<=n;i++){
        cin>>op>>l>>r>>c;
    c%=Mod;
        if(op==0){
            update1(l,r,c);
        }else if(op==1){
            update2(l,r,c);
        }else{
            cout<<query(r)<<"\n";
        }
    }
    return 0;
}

#6284. 数列分块入门 8 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。

技巧

设一个标记 tag 表示这个块被整体设的值，如果这个块被当成散块修改，那么就把这个标记暴力地打下去。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n)，加入一开始把 [1,n] 都设成一个值，那么进行一个区间操作最多破坏首尾 2 个块的标记，所以只能使后面的询问至多多 2 个块的暴力时间，所以均摊每次操作复杂度是 T。最优块长为 \sqrt{n}。

注：这题好像可以用珂朵莉树做，咕咕。

代码

const int N=1e5+5,M=320;
const LL Inf=1e18;
int n,a[N],T,tot,be[M],en[M],bel[N];
LL tag[M];

void init(){
    T=tot=sqrt(n);
    for(int i=1;i<=tot;i++){
        be[i]=en[i-1]+1,en[i]=i*T;
    }
    en[tot]=n;
    for(int i=1;i<=tot;i++){
        tag[i]=Inf;
        for(int j=be[i];j<=en[i];j++){
            bel[j]=i;
        }
    }
}
int cover(int l,int r,int val){
    int res=0;
    if(tag[bel[l]]==Inf){
        for(int i=l;i<=r;i++){
            if(a[i]==val) res++;
            a[i]=val;
        }
    }else if(tag[bel[l]]==val){
        res=r-l+1;
    }else{
        for(int i=be[bel[l]];i<=en[bel[r]];i++){
            if(l<=i&&i<=r) a[i]=val;
            else a[i]=tag[bel[l]];
        }
        tag[bel[l]]=Inf;
    }
    return res;
}
int work(int l,int r,int val){
    if(bel[l]==bel[r]){
        return cover(l,r,val);
    }
    int res=cover(l,en[bel[l]],val)+cover(be[bel[r]],r,val);
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        if(tag[i]==Inf){
            for(int j=be[i];j<=en[i];j++){
                if(a[j]==val) res++;
            }
        }else if(tag[i]==val){
            res+=en[i]-be[i]+1;
        }
        tag[i]=val;
    }
    return res;
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        Cin>>a[i];
    }
    Init();
    For(int i=1,l,r,c;i<=n;i++){
        Cin>>l>>r>>c;
        Cout<<work(l,r,c)<<"\n";
    }
    Return 0;
}

拓展

如果修改和查询操作分开呢？就无法均摊了。这就是 Paint The Wall - HDU 4391。

设 col_{i,x} 表示块 i 内颜色 x 的数量，标记 tag_i 表示块 i 内的数都被赋值成的数。修改散块下传标记后暴力、整块打标记（这里需要修改 col）；查询散块暴力、整块先看有没有 tag，再看 col。

这里空间不够用，就把 col 开成 map。

Const int N=1 e 5+5,M=320;
Int n,m,a[N],T,tot,be[M],en[M],bel[N],tag[M];
map<int,int>col[M];

Void init(){
    T=tot=sqrt(n);
    For(int i=1;i<=tot;i++){
        Be[i]=en[i-1]+1,en[i]=i*T;
    }
    En[tot]=n;
    For(int i=1;i<=tot;i++){
        Tag[i]=-1;
        For(int j=be[i];j<=en[i];j++){
            Bel[j]=i,col[i][a[j]]++;
        }
    }
}
Void pushdown(int bel){
    If(tag[bel]==-1) return;
    For(int i=be[bel];i<=en[bel];i++){
        A[i]=tag[bel];
    }
    Tag[bel]=-1;
}
Void cover(int l,int r,int val){
    If(~tag[bel[l]]) pushdown(bel[l]);
    For(int i=l;i<=r;i++){
        Col[bel[l]][a[i]]--,a[i]=val,col[bel[l]][a[i]]++;
    }
}
Int get(int l,int r,int val){
    If(~tag[bel[l]]) pushdown(bel[l]);
    Int res=0;
    For(int i=l;i<=r;i++){
        If(a[i]==val){
            Res++;
        }
    }
    Return res;
}
Void update(int l,int r,int val){
    If(bel[l]==bel[r]){
        Cover(l,r,val);
        Return;
    }
    Cover(l,en[bel[l]],val),cover(be[bel[r]],r,val);
    For(int i=bel[l]+1;i<=bel[r]-1;i++){
        Col[i].Clear();
        Col[i][val]=en[i]-be[i]+1;
        Tag[i]=val;
    }
}
LL query(int l,int r,int val){
    If(bel[l]==bel[r]){
        Return get(l,r,val);
    }
    LL res=get(l,en[bel[l]],val)+get(be[bel[r]],r,val);
    For(int i=bel[l]+1;i<=bel[r]-1;i++){
        If(col[i].Find(val)!=col[i].End()) res+=col[i][val];
    }
    Return res;
}

Signed main(){
    While(cin>>n>>m){
        For(int i=1;i<=n;i++){
            Cin>>a[i];
        }
        Init();
        For(int i=1,op,l,r,z;i<=m;i++){
            Cin>>op>>l>>r>>z;
            L++,r++;
            If(op==1){
                Update(l,r,z);
            }else{
                Cout<<query(l,r,z)<<"\n";
            }
        }
        For(int i=1;i<=tot;i++){
            Col[i].Clear();
        }
    }
    Return 0;
}

#6285. 数列分块入门 9 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及询问区间的最小众数。

技巧

同 P4168 Violet 蒲公英、P13984 数列分块入门 9 （题解）。若不带修：

• 可以预处理 g_{i,j} 表示 i,j 两块之间的某些信息，这样是 \frac{n}{T}\times\frac{n}{T} 的；
• 也可以预处理 f_i 表示前 i 个块的某些信息，这样是块数 \frac{n}{T} 的，这种如果要修改，说实话也能改，但就是麻烦一点。
• 具体的请看我的这篇题解，LOJ 的本题不需要像洛谷的题那样卡常。

代码

const int N=1e5+5,T=640+5;
int n,m,a[N],L,len,tot,bel[N],be[T],en[T],f[T][T],c[T][N];
vector<int>has,id[N];

void work(int &ans,int &cnt,int Ans,int Cnt){
    if(Cnt>cnt||Cnt==cnt&&Ans<ans){
        cnt=Cnt,ans=Ans;
    }
}
int get(int l,int r,int val){
    return upper_bound(id[val].begin(),id[val].end(),r)-lower_bound(id[val].begin(),id[val].end(),l);
}
void init(){
    L=2*sqrt(n),len=n/max(1,L),tot=L;
    for(int i=1;i<=L;i++){
        be[i]=en[i-1]+1,en[i]=i*len;
    }
    if(en[L]<n){
        tot++;
        be[tot]=en[tot-1]+1;
        en[tot]=n;
    }
    for(int i=1;i<=tot;i++){
        for(int j=be[i];j<=en[i];j++){
            bel[j]=i;
        }
    }
    for(int i=1;i<=tot;i++){
        int ans=0,cnt=0;
        for(int j=be[i];j<=n;j++){
            work(ans,cnt,a[j],++c[i][a[j]]);
            f[i][bel[j]]=ans;
        }
    }
}
int query(int l,int r){
    int ans=0,cnt=0;
    if(bel[l]==bel[r]){
        for(int i=l;i<=r;i++){
            work(ans,cnt,a[i],get(l,r,a[i]));
        }
        return ans;
    }
    if(bel[l]+1<=bel[r]-1){
        work(ans,cnt,f[bel[l]+1][bel[r]-1],get(l,r,f[bel[l]+1][bel[r]-1]));
    }
    for(int i=l;i<=en[bel[l]];i++){
        work(ans,cnt,a[i],get(l,r,a[i]));
    }
    for(int i=be[bel[r]];i<=r;i++){
        work(ans,cnt,a[i],get(l,r,a[i]));
    }
    return ans;
}

signed main(){
    cin>>n;
    m=n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        has.pb(a[i]);
    }
    sort(all(has)),has.erase(unique(all(has)),has.end());
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(all(has),a[i])-has.begin()+1;
        id[a[i]].pb(i);
    }
    init();
    for(int l,r;m--;){
        cin>>l>>r;
        cout<<has[query(l,r)-1]<<"\n";
    }
    return 0;
}

洛谷题目链接

• P13976 数列分块入门 1 - 洛谷
• P13977 数列分块入门 2 - 洛谷
• P13978 数列分块入门 3 - 洛谷
• P13979 数列分块入门 4 - 洛谷
• P13980 数列分块入门 5 - 洛谷
• P13981 数列分块入门 6 - 洛谷
• P13982 数列分块入门 7 - 洛谷
• P13983 数列分块入门 8 - 洛谷
• P13984 数列分块入门 9 - 洛谷

练习题

P3203 HNOI 2010 弹飞绵羊、P5046 Ynoi 2019 模拟赛 Yuno loves sqrt technology I、P4168 Violet 蒲公英。

一些理解和技巧总结

• 与线段树等树形数据结构的对比：
  1. 分块一般时间复杂度是带 \sqrt{n} 的，相对于树形数据结构的 \log n，理论上肯定是不优的。但是由于分块一般操作连续的一段数组，相对于树形数据结构的“跳跃”，计算机硬件处理起来更块。而且分块有个好处，就是可以通过调整块长减小或增大常数。总之，理论复杂度两者差距甚远，但实际表现上来看，分块可能会超出我们的预期，虽然只是“可能”。
  2. 分块就是一些暴力拼在一起，相对来说好写好调。
  3. 分块灵活一点，在上面加一点操作，或者解决一些原本问题的子问题时不会影响时间复杂度，例如上面的数列分块入门 7。
  4. 分块能解决树形数据结构解决不了的问题，具体的，信息不具有区间可加性的问题。
• 分块的块长：如果时间极限，可以固定块长为一个常数，用极限数据试出一个最优的常数（对于不同常数带来的不同时间一般是单谷函数）；
• 分块利用块长的调试：如果不同块长在一个数据下有不同的结果，则说明程序有误（不可代替对拍）；
• 整个块的信息：懒标记（不同于线段树的懒标记，是标记永久化的）、区间和、Paint The Wall - HDU 4391 中的颜色等等；
• 块内元素重排：分完块后，把每个块里的元素重新按照需要的顺序排列。一般是升降序排序，这样就利用单调性等性质了。题目：P10590 磁力块 - 洛谷（分块优化 BFS）、数列分块入门 2、数列分块入门 3；
• 整块信息的利用：一般用于不带修的题目。预处理两块之间的信息，或者块前缀的信息。题目：数列分块入门 9（P4168 Violet 蒲公英）、P5046 Ynoi2019 模拟赛 Yuno loves sqrt technology I、P4135 作诗 - 洛谷；
• 每个位置在块里的信息：预处理每个位置，在它所在块里的某些信息，这样预处理和修改的时间复杂度都只会与块长有关。题目：P 3203 HNOI 2010 弹飞绵羊；
• 用数据结构维护块：每个块都是一个数据结构，比如 set、vector。题目：数列分块入门 3、数列分块入门 6；
• 重新分块（重构）：分为定期重构，和特判重构，数列分块入门 6 中讲的很清楚。时间复杂度可能需要均摊来分析。题目：数列分块入门 6。
• 均摊复杂度：有些题目的操作在进行多次后，会停留在一个定值，我把它称作失效的元素。这时候可以通过记录块内是否都失效，或者记录块内还有多少没失效的元素。暴力，总体复杂度均摊成与序列长度或这值域相关的值。题目：数列分块入门 5、数列分块入门 8；
• 分块的对象：大多数是数列，但有时候是一张图中按点的度数分成度数大于 T 的和小于 T 的。如果点数 n 边数 m 同阶，大点数量只会有 \frac{m}{T} 个。以处理关于邻居的信息为例，小点直接暴力，大点维护，但大点有不会太多，可以保证时间空间复杂度。题目：Finding a MEX - HDU 6756；