2019-08-17 13:09 浙江大学 C++

关注

分块学习笔记

分块学习笔记及入门题选讲

分块是一个很暴力的算法！

咳咳先不提这个。。。

啥是分块：~~分块是一个很暴力的算法~~。分块将所有数据分为若干个块，维护块内信息，使得块内的查询是 $O(1)$ 的，而总的询问就可以看做若干个块询问的总和。一般来讲，块的大小常设为 $sqrt(n)$ ，但实际上块的大小可以任意自定，通过调试来尽可能让复杂度更优。

图：

为什么要分块：因为。。~~分块是一个很暴力的算法~~。它可以完成几乎所有区间更新和区间查询问题 $($ 考场骗分利器 $)$ 。对于小数据，可能效率与线段树相似。虽然大数据可能效率较低，但有些题的确只能用分块做 $($ ~~神仙不管~~ $)$ 。总之，分块的适用性比线段树要广，毕竟是暴力算法

分块实现的基本框架：
划分块，预处理，操作或查询。

操作或查询通常为4步：

1.判断要操作或是查询的区间是否在一个块内

2.若在一个块内，暴力操作或查询

3.若不在一个块内，将除了最左边和最右边这两个块外其余的块进行整体的操作，即直接对块打上修改标记之类的

4.单独暴力处理最左边的块和最右边的块

分块的基础即建块，类比线段树建树。用 $size$ 表示每一块的大小， $num$ 表示一共几块， $belong[i]$ 表示原序列中第 $i$ 个元素在第几块， $l[i],r[i]$ 分别表示第 $i$ 块的左端点和右端点。
上代码：

void build(){
    size=sqrt(n);
    num=n/size;
    if(n%size!=0) num++;//除不尽说明多出一块边角料
    for(int i=1;i<=n;i++) belong[i]=(i-1)/size+1; 
    for(int i=1;i<=num;i++){
        l[i]=(i-1)*size+1;
        r[i]=i*size;
    }
    r[num]=n;//最后一块大小可能不为size,右边界特殊处理 
}

来一道基础题：给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，单点查值。 $(1\leq n\leq 50000)$ LOJ数列分块1

这种题当然可以各种姿势水过去，但我们要学习分块，所以就分块咯。

#include<bits/stdc++.h>
using namespace std;
int n,size,num,belong[100005],l[10005],r[10005],tag[10005],w[100005];
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*ff;
}
void build(){
    size=sqrt(n);
    num=n/size;
    if(n%size!=0) num++;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/size+1; 
    for(int i=1;i<=num;i++){
        l[i]=(i-1)*size+1;
        r[i]=i*size;
    }
    r[num]=n; 
}
void add(int x,int y,int v){
    for(int i=x;i<=min(y,r[belong[x]]);i++) w[i]+=v;//左边边角块 
    if(belong[x]!=belong[y]){//不在同一个块 
        for(int i=(belong[y]-1)*size+1;i<=y;i++)//右边边角块 
            w[i]+=v;
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++) tag[i]+=v;//块整体打标记
}
int query(int x){
    return w[x]+tag[belong[x]];
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++) w[i]=read();
    build();
    for(int i=1;i<=n;i++){
        int opt=read(),x=read(),y=read(),v=read();
        if(opt==0) add(x,y,v);
        else printf("%d\n",query(y));
    }
    return 0;
}

分块也可以水数据小的线段树，LOJ数列分块4

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,size,num,belong[100005],l[10005],r[10005],sum[10005],tag[10005],w[100005];
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*ff;
}
void build(){
    size=sqrt(n);
    num=n/size;
    if(n%size!=0) num++;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/size+1; 
    for(int i=1;i<=num;i++){
        l[i]=(i-1)*size+1;
        r[i]=i*size;
    }
    r[num]=n;
}
void add(int x,int y,int v){
    for(int i=x;i<=min(y,r[belong[x]]);i++) w[i]+=v;//左边边角块
    sum[belong[x]]+=(min(y,r[belong[x]])-x+1)*v;
    if(belong[x]!=belong[y]){//不在同一个块 
        for(int i=(belong[y]-1)*size+1;i<=y;i++) w[i]+=v;
        sum[belong[y]]+=(y-((belong[y]-1)*size+1)+1)*v;
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++) tag[i]+=v,sum[i]+=v*size;
}
int query(int x,int y){
    int res=0;
    for(int i=x;i<=min(y,r[belong[x]]);i++) res+=w[i]+tag[belong[x]];
    if(belong[x]!=belong[y]){ 
        for(int i=(belong[y]-1)*size+1;i<=y;i++) 
            res+=w[i]+tag[belong[y]];
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++) res+=sum[i];
    return res;
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) w[i]=read();
    build();
    for(int i=1;i<=n;i++) sum[belong[i]]+=w[i];
    for(int i=1;i<=m;i++){
        int opt=read(),x=read(),y=read();
        if(opt==1){
            int v=read();
            add(x,y,v);
        }
        else printf("%d\n",query(x,y));
    }
    return 0;
}

~~分块咕了好久了，今天应该会更吧(确信~~

LOJ数列分块2：

给你一个序列，要求资瓷区间加，以及区间查询小于某个数的元素个数。序列长度 $<=50000$

分块怎么考虑？要查询小于某个数的个数，我们可以一个块一个块查，最后把答案合并起来。

那么一个块内怎么查小于某个数的元素个数呢？显然在块内二分，查到第一个大于等于这个数的位置，这个位置的左边一个位置到这个块的左边界就是这个块的答案。二分需要满足单调性，那我们就时刻维护块内元素有序即可。

已经解决了查询的问题，修改还不方便？用分块的基本套路：左右边角块暴力加，中间完整块打标记。我们发现中间完整块整体加一个数，仍旧保持有序，左右暴力加后变成无序，所以加完要再排一遍序。

照着这个思路写完，爆弹了，反复检查没有看出锅，不知道错在哪里。突然发现一个问题：如果我们只用一个数组，排完序后会打乱原有顺序，导致我们想加的数的位置不在原来位置上。

放张图理解一下：

假如这是原来的每个位置上的值（红线代表划分的块），排过序后，变成这样：

这时我们想在位置3上加上一个数（注意是位置），比如加2。按照之前的思路，我们会在当前的位置（第二张图）3上加2，也就是给3加上2，则第一个块变成1,2,5。但实际上，我们应该在第一张图的位置3上加2，第一个块应该是2,3,3，那怎么处理这种情况？也很简单，保留一下原序列，排序在另一个数组上排序，而操作在原序列上操作（原序列不排序）。这样就不会有加错位置的问题了。可以见代码（原序列是t，用来排序的是w）：

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define int long long
#define hh puts("")
using namespace std;
int n,w[50005],belong[50005],sz[10005],t[50005],num,size,tag[10005],l[10005],r[10005];
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
inline void build(){
    size=sqrt(n);
    num=n/size;
    if(n%size) num++;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/size+1;
    for(int i=1;i<=num;i++){
        l[i]=(i-1)*size+1;
        r[i]=i*size;
    }
    r[num]=n;
    for(int i=1;i<=num;i++) sort(w+l[i],w+r[i]+1);
}
inline void add(int x,int y,int v){
    for(int i=x;i<=min(y,r[belong[x]]);i++) t[i]+=v;//在原序列上加
    for(int i=l[belong[x]];i<=r[belong[x]];i++) w[i]=t[i];
    sort(w+l[belong[x]],w+r[belong[x]]+1);
    if(belong[x]!=belong[y]){
        for(int i=l[belong[y]];i<=y;i++) t[i]+=v;
        for(int i=l[belong[y]];i<=r[belong[y]];i++) w[i]=t[i];
        sort(w+l[belong[y]],w+r[belong[y]]+1);
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++) tag[i]+=v;
}
inline int query(int x,int y,int v){
    int res=0,pos;
    for(int i=x;i<=min(y,r[belong[x]]);i++){
        if(t[i]+tag[belong[x]]<v)//对原序列查询
            res++;
    }
    if(belong[x]!=belong[y]){
        for(int i=l[belong[y]];i<=y;i++)
            if(t[i]+tag[belong[y]]<v)
                res++;
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++){
        pos=lower_bound(w+l[i],w+r[i]+1,v-tag[i])-w;
        pos--;//二分找到的是第一个大于等于的，左边一位就是小于的
        res+=pos-l[i]+1;
    }
    return res;
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++) w[i]=read(),t[i]=w[i];
    build();
    for(int i=1;i<=n;i++){
        int opt=read(),L=read(),R=read(),c=read();
        if(opt==0) add(L,R,c);
        else printf("%lld\n",query(L,R,c*c));
    }
    return 0;
}

LOJ数列分块3：

给你一个序列，要求资瓷区间加，以及区间查询小于某个数的最大的数。序列长度 $<=100000$

做完2再做3发现是一样的题，查询时改为取 $max$ 即可：

代码几乎和2一样：

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define int long long
#define hh puts("")
using namespace std;
int n,w[100005],belong[100005],sz[10005],t[100005],num,size,tag[10005],l[10005],r[10005];
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
inline void build(){
    size=sqrt(n);
    num=n/size;
    if(n%size) num++;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/size+1;
    for(int i=1;i<=num;i++){
        l[i]=(i-1)*size+1;
        r[i]=i*size;
    }
    r[num]=n;
    for(int i=1;i<=num;i++) sort(w+l[i],w+r[i]+1);
}
inline void add(int x,int y,int v){
    for(int i=x;i<=min(y,r[belong[x]]);i++) t[i]+=v;
    for(int i=l[belong[x]];i<=r[belong[x]];i++) w[i]=t[i];
    sort(w+l[belong[x]],w+r[belong[x]]+1);
    if(belong[x]!=belong[y]){
        for(int i=l[belong[y]];i<=y;i++) t[i]+=v;
        for(int i=l[belong[y]];i<=r[belong[y]];i++) w[i]=t[i];
        sort(w+l[belong[y]],w+r[belong[y]]+1);
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++) tag[i]+=v;
}
inline int query(int x,int y,int v){
    int res=-1e15,pos;
    for(int i=x;i<=min(y,r[belong[x]]);i++){
        if(t[i]+tag[belong[x]]<v)
            res=max(res,t[i]+tag[belong[x]]);
    }
    if(belong[x]!=belong[y]){
        for(int i=l[belong[y]];i<=y;i++)
            if(t[i]+tag[belong[y]]<v)
                res=max(res,t[i]+tag[belong[y]]);
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++){
        pos=lower_bound(w+l[i],w+r[i]+1,v-tag[i])-w;
        pos--;
        if(pos>=l[i]) res=max(res,w[pos]+tag[i]);
    }
    return res;
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++) w[i]=read(),t[i]=w[i];
    build();
    for(int i=1;i<=n;i++){
        int opt=read(),L=read(),R=read(),c=read();
        if(opt==0) add(L,R,c);
        else{
            int t=query(L,R,c);
            if(t==-1e15) puts("-1");
            else printf("%lld\n",t);
        }
    }
    return 0;
}

LOJ数列分块5：

给你一个序列，要求资瓷区间开方，区间求和。序列长度 $<=50000$

做过[ $GSS4$ ](https://www.luogu.org/problemnew/show/SP2713)，就知道做法了，只不过线段树改分块而已。

发现一个数开方最多开6次，当一段序列最大值为1，显然不需要再开方，分块维护区间和，区间最大值，当区间最大值大于1暴力开方。维护什么应该是基本操作：

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define int long long
#define hh puts("")
using namespace std;
int n,w[50005],size,num,belong[50005],l[10005],r[10005],ma[10005],sum[10005];
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
inline void build(){
    size=sqrt(n);
    num=n/size;
    if(n%size) num++;
    for(int i=1;i<=n;i++){
        belong[i]=(i-1)/size+1;
        ma[belong[i]]=max(ma[belong[i]],w[i]);
        sum[belong[i]]+=w[i];
    }
    for(int i=1;i<=num;i++){
        l[i]=(i-1)*size+1;
        r[i]=i*size;
    }
    r[num]=n;
}
inline void sq(int x,int y){
    if(ma[belong[x]]>1){
        for(int i=x;i<=min(y,r[belong[x]]);i++){
            sum[belong[i]]-=w[i];
            w[i]=sqrt(w[i]);
            sum[belong[i]]+=w[i];
        }
        ma[belong[x]]=0;
        for(int i=l[belong[x]];i<=r[belong[x]];i++) ma[belong[x]]=max(ma[belong[x]],w[i]);
    }
    if(belong[x]!=belong[y]){
        if(ma[belong[y]]>1){
            for(int i=l[belong[y]];i<=y;i++){
                sum[belong[y]]-=w[i];
                w[i]=sqrt(w[i]);
                sum[belong[y]]+=w[i];
            }
            ma[belong[y]]=0;
            for(int i=l[belong[y]];i<=r[belong[y]];i++) ma[belong[y]]=max(ma[belong[y]],w[i]);
        }
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++){
        if(ma[i]>1){
            ma[i]=0;
            for(int j=l[i];j<=r[i];j++){
                sum[i]-=w[j];
                w[j]=sqrt(w[j]);
                ma[i]=max(ma[i],w[j]);
                sum[i]+=w[j];
            }
        }
    }
}
inline int query(int x,int y){
    int res=0;
    for(int i=x;i<=min(y,r[belong[x]]);i++) res+=w[i];
    if(belong[x]!=belong[y])
        for(int i=l[belong[y]];i<=y;i++)
            res+=w[i];
    for(int i=belong[x]+1;i<=belong[y]-1;i++) res+=sum[i];
    return res;
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++) w[i]=read();
    build();
    for(int i=1;i<=n;i++){
        int opt=read(),L=read(),R=read(),cccc=read();
        if(opt==0) sq(L,R);
        else printf("%lld\n",query(L,R));
    }
    return 0;
}

LOJ数列分块6：

给定一个序列，资瓷插入元素，以及查询某一位置元素的值。

用 $vector$ 自带的 $insert$ 函数水过去了 $($ ~~STLnb~~ $)$ ，当然每一次 $insert$ 都是 $O(n)$ 的，~~为什么我们直接插入没有被卡？很简单，因为数据随机。~~我们考虑用分块怎么做。

如果用分块，口胡一下，代码没写：我们用 $vector$ 来存同一个块内的元素，对于插入操作，先根据每一块的大小，找到要插元素应该插入的块，然后利用 $vector$ 的 $insert$ 函数进行插入。查询同理。

这时有一个问题，会有~~sangxinbingkuang~~的出题人来卡你，怎么卡？在同一个块内不断插入元素，使一个块变的特别大。怎么办？

那我们就限定一个块大小的阈值，超过这个阈值，我们重新分块即可。这样就可以保证复杂度正确。

还是给一下暴力代码（逃：

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define ll long long
#define hh puts("")
using namespace std;
int n;
vector<int> v;
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++) v.push_back(read());
    for(int i=1;i<=n;i++){
        int opt=read(),l=read(),r=read(),c=read();
        if(opt==0) v.insert(v.begin()+l-1,r);
        else printf("%d\n",v[r-1]);
    }
    return 0;
}

LOJ数列分块7：

给你一个序列，要求资瓷区间加，区间乘，单点求值。序列长度 $<=100000$

打两个标记，加法标记和乘法标记。区间操作时，如果是边角块，我们对整个块标记全部下放，然后暴力修改边角。如果是整块，分两种情况：先乘后加，先加后乘。

先乘后加，对两个标记分别操作即可，互不干扰。但如果先加后乘，则乘法对加法标记有影响。设原来乘法标记为 $a$ ，加法标记为 $b$ ，一个数为 $x$ ，则原来值为 $ax+b$ ，乘上一个数 $k$ ，则值变成 $akx+bk$ ，所以乘的时候，对加法标记也进行乘操作即可。

具体见代码：

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define int long long
#define hh puts("")
#define mo 10007
using namespace std;
int n,size,num,w[100005],belong[100005],l[10005],r[10005],tag_mul[10005],tag_add[10005];
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
inline void build(){
    size=sqrt(n);
    num=n/size;
    if(n%size) num++;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/size+1;
    for(int i=1;i<=num;i++){
        l[i]=(i-1)*size+1;
        r[i]=i*size;
        tag_mul[i]=1;//注意乘法标记一开始是1不是0
        tag_add[i]=0;
    }
    r[num]=n;
}
inline void add(int x,int y,int v){
    for(int i=l[belong[x]];i<=r[belong[x]];i++){//把整个块标记全部下放 
        w[i]=((w[i]*tag_mul[belong[x]]%mo)+tag_add[belong[x]])%mo;
    }
    for(int i=x;i<=min(y,r[belong[x]]);i++) w[i]=(w[i]+v)%mo;
    tag_mul[belong[x]]=1;
    tag_add[belong[x]]=0;
    if(belong[x]!=belong[y]){
        for(int i=l[belong[y]];i<=r[belong[y]];i++){
            w[i]=((w[i]*tag_mul[belong[y]]%mo)+tag_add[belong[y]])%mo;
        }
        for(int i=l[belong[y]];i<=y;i++) w[i]=(w[i]+v)%mo;
        tag_mul[belong[y]]=1;
        tag_add[belong[y]]=0;
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++) tag_add[i]=(tag_add[i]+v)%mo;
}
inline void mul(int x,int y,int v){
    for(int i=l[belong[x]];i<=r[belong[x]];i++){
        w[i]=((w[i]*tag_mul[belong[x]]%mo)+tag_add[belong[x]])%mo;
    }
    for(int i=x;i<=min(y,r[belong[x]]);i++) w[i]=w[i]*v%mo;
    tag_mul[belong[x]]=1;
    tag_add[belong[x]]=0;
    if(belong[x]!=belong[y]){
        for(int i=l[belong[y]];i<=r[belong[y]];i++){
            w[i]=((w[i]*tag_mul[belong[y]]%mo)+tag_add[belong[y]])%mo;
        }
        for(int i=l[belong[y]];i<=y;i++) w[i]=w[i]*v%mo;
        tag_mul[belong[y]]=1;
        tag_add[belong[y]]=0;
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++){
        tag_add[i]=tag_add[i]*v%mo;//对加法标记也进行乘操作
        tag_mul[i]=tag_mul[i]*v%mo;
    }
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++) w[i]=read();
    build();
    for(int i=1;i<=n;i++){
        int opt=read(),L=read(),R=read(),c=read();
        if(opt==0) add(L,R,c);
        else if(opt==1) mul(L,R,c);
        else printf("%lld\n",((w[R]*tag_mul[belong[R]]%mo)+tag_add[belong[R]])%mo);
    }
    return 0;
}

LOJ数列分块8：
给你一个序列，每次操作查询一段区间等于某个数 $x$ 的数的个数，并把这段区间改成 $x$ 。序列长度 $<=100000$

做法和 $hzwer$ 的不太一样。讲一下我的方法：

考虑和数列分块2一样的做法，如果一个块内是有序的，那么我们可以通过二分查找等于 $c$ 的个数，具体怎么找呢？我们先用 $lowerbound$ ，找到大于等于 $c$ 的第一个数，如果这个数不等于 $c$ ，或者这个块内最大数也没 $c$ 大，显然这个区间没有等于 $c$ 的数，否则我们设找到的左端点为 $L$ 。如果这个区间有等于 $c$ 的数，我们再 $upperbound$ ，找到第一个大于 $c$ 的位置，这个位置的左边一个位置，我们设为 $R$ ，那么现在， $L$ 到 $R$ 之间的数都等于 $c$ ， $c$ 的个数就是 $R-L+1$ 。

对于修改操作，我们仍旧采用边角块暴力修改，完整块打标记。这里的标记我们分两种，一种随便取个值，表示这个块内数值都不相同（我取了 $-1e9$ ），另一种就表示这个块内数值都等于这个标记。

查询边角块注意事项：边角块暴力查询之前，要把整个块都变成标记表示的数值（如果有标记），暴力修改后，这个块标记赋值为 $-1e9$ ，并对这个块排序。完整块就按之前讲的来。

和数列分块2一样，为了防止排序造成的位置变动，我们也用一个 $t$ 数组记录没排序的数组来进行暴力操作。

分析一下复杂度，貌似是 $O(n\ log \ n+n\times (\sqrt{n}+\sqrt{n}\ log \ \sqrt{n}))$ （不知道对不对，我太菜不会分析复杂度）。显然需要卡常技巧，效率肯定没 $hzwer$ 的做法高，我开 $O2$ 才水过去的。

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define ll long long
#define hh puts("")
using namespace std;
int n,size,num,w[100005],t[100005],belong[100005],l[10005],r[10005],tag[10005];
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
inline void build(){
    size=sqrt(n);
    num=n/size;
    if(n%size) num++;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/size+1;
    for(int i=1;i<=num;i++){
        l[i]=(i-1)*size+1;
        r[i]=i*size;
        tag[i]=-1e9;
    }
    r[num]=n;
    for(int i=1;i<=num;i++) sort(w+l[i],w+r[i]+1);
}
inline int query(int x,int y,int c){
    int res=0;
    if(tag[belong[x]]!=-1e9) for(int i=l[belong[x]];i<=r[belong[x]];i++) t[i]=tag[belong[x]];
    for(int i=x;i<=min(y,r[belong[x]]);i++)
        if(t[i]==c)
            res++;
    if(belong[x]!=belong[y]){
        if(tag[belong[y]]!=-1e9) for(int i=l[belong[y]];i<=r[belong[y]];i++) t[i]=tag[belong[y]];
        for(int i=l[belong[y]];i<=y;i++)
            if(t[i]==c)
                res++;
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++){
        if(tag[i]==-1e9){
            int pos1=lower_bound(w+l[i],w+r[i]+1,c)-w;
            if(pos1==r[i]+1) continue;
            if(w[pos1]!=c) continue;
            int pos2=upper_bound(w+l[i],w+r[i]+1,c)-w;
            res+=pos2-pos1;
        }
        else if(tag[i]==c) res+=r[i]-l[i]+1;
    }
    return res;
}
inline void update(int x,int y,int c){
    for(int i=x;i<=min(y,r[belong[x]]);i++) t[i]=c;
    for(int i=l[belong[x]];i<=r[belong[x]];i++) w[i]=t[i];
    sort(w+l[belong[x]],w+r[belong[x]]+1);
    tag[belong[x]]=-1e9;
    if(belong[x]!=belong[y]){
        for(int i=l[belong[y]];i<=y;i++) t[i]=c;
        for(int i=l[belong[y]];i<=r[belong[y]];i++) w[i]=t[i];
        sort(w+l[belong[y]],w+r[belong[y]]+1);
        tag[belong[y]]=-1e9;
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++) tag[i]=c;
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++) w[i]=read(),t[i]=w[i];
    build();
    for(int i=1;i<=n;i++){
        int L=read(),R=read(),c=read();
        printf("%d\n",query(L,R,c));
        update(L,R,c);
    }
    return 0;
}

LOJ数列分块9：

给你一个序列，每次操作查询一段区间的最小众数。序列长度 $<=100000$

先给出我的 $O(n \ log \ n+n\sqrt{n} \ log \ n)$ 的做法。(但是~~因为我菜~~常数实在太大了 $LOJ$ 跑不过去)

显然先把数离散化，我用的 $map$ ，复杂度 $O(n\ log \ n)$ ，然后我们预处理出每两个块区间的众数，用桶暴力统计，复杂度 $O(n\sqrt{n})$ 。对于每一个询问，因为中间完整块的众数我们已经统计出，所以我们只要判断边角块的数可不可能成为众数。

暴力判断每一个数，怎么统计 $l$ 到 $r$ 之间某个数出现了几次？我们初始化时将每一个数出现的位置用 $vector$ 存下来，然后对于边角块的每一个数，在 $vector$ 内二分查找 $l$ 和 $r$ ，两者相减即可。这样我们就判断了所有情况，边角块大小 $O(\sqrt{n})$ ，查询复杂度每次 $O(log \ n)$ ，询问个数 $O(n)$ ，询问总复杂度 $O(n\sqrt{n} \ log \ n)$ 。

常数极大的代码（调到自闭都没过）：

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define ll long long
#define hh puts("")
using namespace std;
int belong[100005],a[100005],n,m,size,num,val[100005],id,maxx[505][505],tot[100005];
int l[1005],r[1005],vis[100005];
vector<int> v[100005];
map<int,int> ma;
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
inline void init(int x){//预处理每两块之间的众数
    int count=0,mx=0;
    for(int i=(x-1)*size+1;i<=n;i++){
        tot[a[i]]++;
        if(tot[a[i]]>count||(tot[a[i]]==count&&val[a[i]]<val[mx])){
            count=tot[a[i]];
            mx=a[i];
        }
        maxx[x][belong[i]]=mx;
    }
    for(int i=(x-1)*size+1;i<=n;i++) tot[a[i]]=0;
}
inline int check(int l,int r,int c){
    return upper_bound(v[c].begin(),v[c].end(),r)-lower_bound(v[c].begin(),v[c].end(),l);
}
inline int work(int x,int y){
    int ans=maxx[belong[x]+1][belong[y]-1],count=0,tt;
    vis[ans]=1;
    tt=ans;
    count=check(x,y,ans);
    for(int i=x;i<=min(y,belong[x]*size);i++){
        if(!vis[a[i]]){
            vis[a[i]]=1;
            int t=check(x,y,a[i]);
            if(t>count||(t==count&&val[a[i]]<val[ans])){
                ans=a[i];
                count=t;
            }
        }
    }
    if(belong[x]!=belong[y]){
        for(int i=(belong[y]-1)*size+1;i<=y;i++){
            if(!vis[a[i]]){
                vis[a[i]]=1;
                int t=check(x,y,a[i]);
                if(t>count||(t==count&&val[a[i]]<val[ans])){
                    count=t;
                    ans=a[i];
                }
            }
        }
        for(int i=(belong[y]-1)*size+1;i<=y;i++) vis[a[i]]=0;
    }
    for(int i=x;i<=min(y,belong[x]*size);i++) vis[a[i]]=0;
    vis[tt]=0;
    return val[ans];
}
signed main(){
    n=read();
    size=sqrt(n);
    num=n/size;
    for(int i=1;i<=n;i++){
        a[i]=read();
        belong[i]=(i-1)/size+1;
        if(ma[a[i]]==0){
            ma[a[i]]=++id;
            val[id]=a[i];//编号对应的值
        }
        a[i]=ma[a[i]];//离散化
        v[a[i]].push_back(i);
    }
    for(int i=1;i<=num;i++) init(i);
    for(int i=1;i<=n;i++){
        int x=read(),y=read();
        printf("%d\n",work(x,y));
    }
    return 0;
}

没过啊怎么办？只能优化对不对。看着这只 $log$ 我们感到它非常欠 $A$ ，它让我们复杂度多了十几倍，那我们就把它 $A$ 掉。要搞掉这只 $log$ ，也就是说我们处理边角块的复杂度要到 $O(\sqrt{n})$ ，不能对每个数都暴力处理，而是进行线性操作。

怎么操作呢？我们可以对当前的答案（即当前众数个数）进行判断，在预处理时我们记录每种颜色在同种颜色位置序列中是第几个，存在 $pos$ 数组里，如果不懂的话可以看下代码。（因为是 $vector$ 里所以下标从0开始）暴力处理边角块时，设我们在处理左边角块，设当前众数出现了 $count$ 次，当前处理的数在整个序列中下标为 $i$ ，则如果当前数 $a[i]$ 是区间的众数，一定满足

$pos[i]+count-1>=0$

$pos[i]+count-1<v[a[i]].size()$

$v[a[i]][pos[i]+count-1]>=x$

$v[a[i]][pos[i]+count-1]<=y$

（ $v$ 是存离散编号的数的位置的容器， $v[i]$ 存编号为 $i$ 的数在序列中的位置， $x,y$ 是询问区间）。不是很容易理解，可以看代码理解一下。

如果这些条件都满足，判一下和当前 $ans$ 的值，谁小就取谁。

处理右边角块时则是 $pos[i]-count+1$ 。

代码：

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define ll long long
#define hh puts("")
using namespace std;
int belong[100005],a[100005],n,m,size,num,val[100005],id,maxx[505][505],f[505][505],tot[100005],pos[100005];
int l[1005],r[1005];
vector<int> v[100005];
map<int,int> ma;
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-ff;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
inline void init(int x){//预处理每两块之间的众数
    int count=0,mx=0;
    for(int i=l[x];i<=n;i++){
        tot[a[i]]++;
        if(tot[a[i]]>count||(tot[a[i]]==count&&val[a[i]]<val[mx])){
            count=tot[a[i]];
            mx=a[i];
        }
        maxx[x][belong[i]]=mx;//哪一个众数
        f[x][belong[i]]=count;//出现次数
    }
    for(int i=l[belong[x]];i<=n;i++) tot[a[i]]=0;
}
inline int work(int x,int y){
    int ans=maxx[belong[x]+1][belong[y]-1],count=f[belong[x]+1][belong[y]-1];//ans:哪一个众数,count:出现了几次
    for(int i=x;i<=min(y,r[belong[x]]);i++){
        if(pos[i]+count-1>=0&&pos[i]+count-1<(int)v[a[i]].size()&&v[a[i]][pos[i]+count-1]>=x&&v[a[i]][pos[i]+count-1]<=y)
            if(val[a[i]]<val[ans])
                ans=a[i];
        for(;pos[i]+count<(int)v[a[i]].size()&&v[a[i]][pos[i]+count]<=y;++count) ans=a[i];
    }
    if(belong[x]!=belong[y]){
        for(int i=l[belong[y]];i<=y;i++){
            if(pos[i]-count+1>=0&&pos[i]-count+1<(int)v[a[i]].size()&&v[a[i]][pos[i]-count+1]>=x&&v[a[i]][pos[i]-count+1]<=y)
                if(val[a[i]]<val[ans])
                    ans=a[i];
            for(;pos[i]-count>=0&&v[a[i]][pos[i]-count]>=x;++count) ans=a[i];
        }
    }
    return val[ans];
}
inline void write(int x){
    if(x>9) write(x/10);
    putchar(x%10+48);
}
signed main(){
    n=read();
    size=sqrt(n);
    num=n/size;
    if(n%size) num++;
    for(int i=1;i<=n;i++){
        a[i]=read();
        belong[i]=(i-1)/size+1;
        if(ma[a[i]]==0){
            ma[a[i]]=++id;
            val[id]=a[i];//编号对应的值
        }
        a[i]=ma[a[i]];//离散化
        pos[i]=v[a[i]].size();
        v[a[i]].push_back(i);
    }
    for(int i=1;i<=num;i++){
        l[i]=(i-1)*size+1;
        r[i]=i*size;
    }
    r[num]=n;
    for(int i=1;i<=num;i++) init(i);
    for(int i=1;i<=n;i++){
        int x=read(),y=read();
        write(work(x,y));
        hh;
    }
    return 0;
}

总之最后一题是最难的，可能分析的并不是很好。

至此我们做完了 $LOJ$ 数列分块9题，完结撒花~。

$hzwer$ 的题还是挺不错的，做完后对分块的基本认识肯定更深一点，对分块的基本代码也巩固了，之后的话 $\cdots$ 听说 $ynoi$ 的题很有意思，去玩一玩（~~被毒死~~）？