以前一直听说分块啥的…感觉不明觉厉…昨天晚上突发奇想想学习一下然后搜博客的时候发现了qscqesze的bilbili视频…讲得真好orz虽然很久之前就关注他了但是没有好好看过他的视频orz

传送门：https://www.bilibili.com/video/av6445624/

昨天晚上看完的今天早上就迫不及待敲一发找到了loj上hzwer的数列分块入门打算都做一遍hhh

分块是什么呢？就是把一个大块拆成若干个小块进行计算，每个小块有可能有一些共同特点，或者每个小块内部是有顺序的，这样，在修改操作的时候，只需要算出两边的节点所属的小块的编号分别是什么，然后两边的散块可以进行暴力修改，而中间的由于题目不同，可以进行不同的操作，比如说区间加，那么就可以在中间的每个小块上面直接像线段树一样打一个lazy标记，标记区间增加了多少。然后在查询的时候就可以直接对散块进行暴力查询，然后对整块运用之前设置的lazy标记，或者保证有序后用二分进行从O（n）进行到O（log（n））的优化。

build函数

int n;
long long a[50010];
int num;//分块的个数
int belong[50010];//每个数属于哪个分块
int block;//每个块的大小
int lef[50010],rig[50010];//该块的左/右端点位置
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
        lef[i]=(i-1)*block+1,rig[i]=i*block;
    rig[num]=n;//最后一块不满的情况
}

LOJ 6277

题意：若 opt=0，表示将位于[l,r]的之间的数字都加c。

若 opt=1，表示询问ar的值（l和c忽略）。

思路：加一个数组表示每个块一起又加了多少即可。

代码：

int n;
long long a[50010];
int num;//分块的个数
int belong[50010];//每个数属于哪个分块
int block;//每个块的大小
int lef[50010],rig[50010];//该块的左/右端点位置
long long d[50010];//每个块一起又加了多少
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    for(int i=1;i<=num;i++)
        lef[i]=(i-1)*block+1,rig[i]=i*block;
    rig[num]=n;//最后一块不满的情况
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
}
void update(int l,int r,int c)//区间更新
{
    if(belong[l]==belong[r])
    {
        for(int i=l;i<=r;i++)
            a[i]+=c;
    }
    else
    {
        //printf("%d %d %d %d\n",belong[l],belong[r],rig[belong[l]],lef[belong[r]]);
        for(int i=l;i<=rig[belong[l]];i++)
            a[i]+=c;
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
            d[i]+=c;
        for(int i=lef[belong[r]];i<=r;i++)
            a[i]+=c;
    }
}
void ask(int x)//单点询问
{
    printf("%lld\n",a[x]+d[belong[x]]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build();
    memset(d,0,sizeof(d));
    int ope,l,r,c;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d%d",&ope,&l,&r,&c);
        if(ope==0)update(l,r,c);
        else if(ope==1)ask(r);
    }
    return 0;
}

LOJ 6278

题意：若 opt=0，表示将位于[l,r] 的之间的数字都加 c。

若 opt=1，表示询问 [l,r] 中，小于 c^2 的数字的个数。

思路：

对于每次区间操作：

1.不完整的块 的O(√n)个元素怎么处理？

2.O(√n)个 整块 怎么处理？

3.要预处理什么信息（复杂度不能超过后面的操作）？

在块内维护升序数组b。

考虑到加c之后，块内的升序是不会发生改变的，但是块外是会有改变的，所以要维护块外的升序。

当询问时，块外的顺序已经乱了，b[i]的编号与询问的编号是不同的，所以不能直接根据b[i]来二分，而要暴力查询；而块内则无所谓顺序，因为都在[l,r]的范围之内，只需知道有几个，直接在b上二分即可。

代码：

int n;
long long a[50010];
long long b[50010];//块内排序
int num;//分块的个数
int belong[50010];//每个数属于哪个分块
int block;//每个块的大小
int lef[50010],rig[50010];//该块的左/右端点位置
long long d[50010];//每个块一起又加了多少
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    for(int i=1;i<=n;i++)
    {
        belong[i]=(i-1)/block+1;
        b[i]=a[i];
    }
    for(int i=1;i<=num;i++)
    {
        lef[i]=(i-1)*block+1,rig[i]=i*block;
        if(i==num)rig[i]=n;//最后一块不满的情况
        sort(b+lef[i],b+rig[i]+1);//块内维护升序
    }
    /*for(int i=1;i<=n;i++)
        printf("%lld ",b[i]);
    printf("\n");*/
}
void update(int l,int r,long long c)//区间更新
{
    if(belong[l]==belong[r])
    {
        for(int i=l;i<=r;i++)
            a[i]+=c;
        for(int i=lef[belong[l]];i<=rig[belong[l]];i++)//更新b[i]
            b[i]=a[i];
        sort(b+lef[belong[l]],b+rig[belong[l]]+1);//块内维护升序
    }
    else
    {
        //printf("%d %d %d %d\n",belong[l],belong[r],rig[belong[l]],lef[belong[r]]);
        for(int i=l;i<=rig[belong[l]];i++)
            a[i]+=c;
        for(int i=lef[belong[l]];i<=rig[belong[l]];i++)//更新b[i]
            b[i]=a[i];
        sort(b+lef[belong[l]],b+rig[belong[l]]+1);
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
            d[i]+=c;
        for(int i=lef[belong[r]];i<=r;i++)
            a[i]+=c;
        for(int i=lef[belong[r]];i<=rig[belong[r]];i++)
            b[i]=a[i];
        sort(b+lef[belong[r]],b+rig[belong[r]]+1);
    }
    /*for(int i=1;i<=n;i++)
        printf("%lld ",b[i]);
    printf("\n");*/
}
void ask(int l,int r,long long st)//区间询问
{
    int ans=0;
    if(belong[l]==belong[r])
    {
        for(int i=l;i<=r;i++)
            if(a[i]+d[belong[l]]<st)
                ans++;
    }
    else
    {
        for(int i=l;i<=rig[belong[l]];i++)
            if(a[i]+d[belong[l]]<st)
                ans++;
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
        {
            int pos=lower_bound(b+lef[i],b+rig[i]+1,st-d[i])-b;
            ans+=pos-lef[i];
        }
        for(int i=lef[belong[r]];i<=r;i++)
            if(a[i]+d[belong[r]]<st)
                ans++;
    }
    printf("%d\n",ans);
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build();
    memset(d,0,sizeof(d));
    int ope,l,r;
    long long c;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d%lld",&ope,&l,&r,&c);
        if(ope==0)update(l,r,c);
        else if(ope==1)ask(l,r,c*c);
    }
    return 0;
}

LOJ 6279

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

思路：跟上一题差不多区间询问的地方稍微改一下就可以了。

可以在块内维护其它结构使其更具有拓展性，比如放一个set，这样如果还有插入、删除元素的操作，会更加的方便。

分块的调试检测技巧：可以生成一些大数据，然后用两份分块大小不同的代码来对拍，还可以根据运行时间尝试调整分块大小，减小常数。

代码：

int n;
long long a[100010];
long long b[100010];//块内排序
int num;//分块的个数
int belong[100010];//每个数属于哪个分块
int block;//每个块的大小
int lef[100010],rig[100010];//该块的左/右端点位置
long long d[100010];//每个块一起又加了多少
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    for(int i=1;i<=n;i++)
    {
        belong[i]=(i-1)/block+1;
        b[i]=a[i];
    }
    for(int i=1;i<=num;i++)
    {
        lef[i]=(i-1)*block+1,rig[i]=i*block;
        if(i==num)rig[i]=n;//最后一块不满的情况
        sort(b+lef[i],b+rig[i]+1);//块内维护升序
    }
    /*for(int i=1;i<=n;i++)
        printf("%lld ",b[i]);
    printf("\n");*/
}
void update(int l,int r,long long c)//区间更新
{
    if(belong[l]==belong[r])
    {
        for(int i=l;i<=r;i++)
            a[i]+=c;
        for(int i=lef[belong[l]];i<=rig[belong[l]];i++)//更新b[i]
            b[i]=a[i];
        sort(b+lef[belong[l]],b+rig[belong[l]]+1);//块内维护升序
    }
    else
    {
        //printf("%d %d %d %d\n",belong[l],belong[r],rig[belong[l]],lef[belong[r]]);
        for(int i=l;i<=rig[belong[l]];i++)
            a[i]+=c;
        for(int i=lef[belong[l]];i<=rig[belong[l]];i++)//更新b[i]
            b[i]=a[i];
        sort(b+lef[belong[l]],b+rig[belong[l]]+1);
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
            d[i]+=c;
        for(int i=lef[belong[r]];i<=r;i++)
            a[i]+=c;
        for(int i=lef[belong[r]];i<=rig[belong[r]];i++)
            b[i]=a[i];
        sort(b+lef[belong[r]],b+rig[belong[r]]+1);
    }
    /*for(int i=1;i<=n;i++)
        printf("%lld ",a[i]+d[belong[i]]);
    printf("\n");*/
}
void ask(int l,int r,long long st)//区间询问
{
    long long cur=-INF;
    if(belong[l]==belong[r])
    {
        for(int i=l;i<=r;i++)
        {
            long long zs=a[i]+d[belong[l]];
            if(zs<st&&zs>cur)
                cur=zs;
        }
    }
    else
    {
        for(int i=l;i<=rig[belong[l]];i++)
        {
            long long zs=a[i]+d[belong[l]];
            if(zs<st&&zs>cur)
                cur=zs;
        }
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
        {
            int pos=lower_bound(b+lef[i],b+rig[i]+1,st-d[i])-b;
            long long zs=b[pos-1]+d[i];
            if(pos-1>=lef[i]&&zs<st&&zs>cur)
                cur=zs;
        }
        for(int i=lef[belong[r]];i<=r;i++)
        {
            long long zs=a[i]+d[belong[r]];
            if(zs<st&&zs>cur)
                cur=zs;
        }
    }
    if(cur==-INF)printf("-1\n");
    else printf("%lld\n",cur);
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build();
    memset(d,0,sizeof(d));
    int ope,l,r;
    long long c;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d%lld",&ope,&l,&r,&c);
        if(ope==0)update(l,r,c);
        else if(ope==1)ask(l,r,c);
    }
    return 0;
}

LOJ 6280

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

思路：加两个数组表示每个块的总和（用前缀和处理），表示每个块又加了多少，维护区间和即可。

代码：

int n;
long long a[50010];
int num;//分块的个数
int belong[50010];//每个数属于哪个分块
int block;//每个块的大小
int lef[50010],rig[50010];//该块的左/右端点位置
long long pre[50010];//前缀和
long long sum[50010];//每个块的总和
long long d[50010];//每个块一起又加了多少
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    pre[0]=0;
    for(int i=1;i<=n;i++)
    {
        belong[i]=(i-1)/block+1;
        pre[i]=pre[i-1]+a[i];
    }
    for(int i=1;i<=num;i++)
    {
        lef[i]=(i-1)*block+1,rig[i]=i*block;
        if(i==num)rig[i]=n;//最后一块不满的情况
        sum[i]=pre[rig[i]]-pre[lef[i]-1];
    }
    /*for(int i=1;i<=num;i++)
        printf("%lld ",sum[i]);
    printf("\n");*/
}
void update(int l,int r,long long c)//区间更新
{
    if(belong[l]==belong[r])
    {
        for(int i=l;i<=r;i++)
            a[i]+=c,sum[belong[l]]+=c;//维护区间和
    }
    else
    {
        //printf("%d %d %d %d\n",belong[l],belong[r],rig[belong[l]],lef[belong[r]]);
        for(int i=l;i<=rig[belong[l]];i++)
            a[i]+=c,sum[belong[l]]+=c;
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
            d[i]+=c;
        for(int i=lef[belong[r]];i<=r;i++)
            a[i]+=c,sum[belong[r]]+=c;
    }
}
void ask(int l,int r,long long modd)//区间询问
{
    long long ans=0;
    if(belong[l]==belong[r])
    {
        for(int i=l;i<=r;i++)
            ans=(ans+a[i]+d[belong[l]])%modd;
    }
    else
    {
        for(int i=l;i<=rig[belong[l]];i++)
            ans=(ans+a[i]+d[belong[l]])%modd;
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
            ans=(ans+sum[i]+(d[i]*block)%modd)%modd;
        for(int i=lef[belong[r]];i<=r;i++)
            ans=(ans+a[i]+d[belong[r]])%modd;
    }
    printf("%lld\n",ans);
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build();
    memset(d,0,sizeof(d));
    int ope,l,r;
    long long c;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d%lld",&ope,&l,&r,&c);
        if(ope==0)update(l,r,c);
        else if(ope==1)ask(l,r,c+1);
    }
    return 0;
}

LOJ 6281

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

思路：跟以前做过的一道线段树差不多，那道线段树没有用到lazy标记，这里也差不多，不能直接像上面那题区间求和，要利用开方，开个bool数组标记每个块是否还可以开方，如果都是0或1的话就不能开方了，这里还是用到sum数组，查询的时候会快点。

代码：

int n;
long long a[50010];
int num;//分块的个数
int belong[50010];//每个数属于哪个分块
int block;//每个块的大小
int lef[50010],rig[50010];//该块的左/右端点位置
bool can[50010];//每个块是否还可以开方
long long pre[50010];
long long sum[50010];//每个块的和
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    pre[0]=0;
    for(int i=1;i<=n;i++)
    {
        belong[i]=(i-1)/block+1;
        can[i]=true;
        pre[i]=pre[i-1]+a[i];
    }
    for(int i=1;i<=num;i++)
    {
        lef[i]=(i-1)*block+1,rig[i]=i*block;
        if(i==num)rig[i]=n;//最后一块不满的情况
        sum[i]=pre[rig[i]]-pre[lef[i]-1];
    }
    /*for(int i=1;i<=num;i++)
        printf("%lld ",sum[i]);
    printf("\n");*/
}
void update(int l,int r,long long c)//区间更新
{
    if(belong[l]==belong[r])
    {
        if(can[belong[l]])
        {
            for(int i=l;i<=r;i++)
            {
                sum[belong[l]]=sum[belong[l]]-a[i]+sqrt(a[i]);
                a[i]=sqrt(a[i]);
            }
            bool sign=false;
            for(int i=lef[belong[l]];i<=rig[belong[l]]&&!sign;i++)
                if(a[i]!=0&&a[i]!=1)sign=true;
            if(!sign)can[belong[l]]=false;
        }
    }
    else
    {
        if(can[belong[l]])
        {
            for(int i=l;i<=rig[belong[l]];i++)
            {
                sum[belong[l]]=sum[belong[l]]-a[i]+sqrt(a[i]);
                a[i]=sqrt(a[i]);
            }
            bool sign=false;
            for(int i=lef[belong[l]];i<=rig[belong[l]]&&!sign;i++)
                if(a[i]!=0&&a[i]!=1)sign=true;
            if(!sign)can[belong[l]]=false;
        }
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
        {
            if(can[i])
            {
                for(int j=lef[i];j<=rig[i];j++)
                {
                    sum[i]=sum[i]-a[j]+sqrt(a[j]);
                    a[j]=sqrt(a[j]);
                }
                bool sign=false;
                for(int j=lef[i];j<=rig[i]&&!sign;j++)
                    if(a[j]!=0&&a[j]!=1)sign=true;
                if(!sign)can[i]=false;
            }
        }
        if(can[belong[r]])
        {
            for(int i=lef[belong[r]];i<=r;i++)
            {
                sum[belong[r]]=sum[belong[r]]-a[i]+sqrt(a[i]);
                a[i]=sqrt(a[i]);
            }
            bool sign=false;
            for(int i=lef[belong[r]];i<=rig[belong[r]]&&!sign;i++)
                if(a[i]!=0&&a[i]!=1)sign=true;
            if(!sign)can[belong[r]]=false;
        }
    }
}
void ask(int l,int r,long long c)//区间询问
{
    long long ans=0;
    if(belong[l]==belong[r])
        for(int i=l;i<=r;i++)
            ans+=a[i];
    else
    {
        for(int i=l;i<=rig[belong[l]];i++)
            ans+=a[i];
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
            ans+=sum[i];
        for(int i=lef[belong[r]];i<=r;i++)
            ans+=a[i];
    }
    printf("%lld\n",ans);
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build();
    int ope,l,r;
    long long c;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d%lld",&ope,&l,&r,&c);
        if(ope==0)update(l,r,c);
        else if(ope==1)ask(l,r,c+1);
    }
    return 0;
}

LOJ 6282

题意：给出一个长为 n 的数列，以及 n 个操作，操作涉及单点插入，单点询问，数据随机生成。

思路：每个块放入vector内，插入的时候用insert函数实现，但是如果先在一个块有大量单点插入，这个块的大小会大大超过√n，块内的插入就很慢了，所以还需要引入一个操作：重新分块（重构），每√n次插入后，重新把数列平均分一下块。

我这里有个很奇怪的地方，rebuild()这个函数里面，我直接用覆盖n的方法会WA，但是另外用个变量就AC了，不知道错在哪里，真的很奇怪…

代码：

int n;
int num;
int block;
int a[100010];
int zs[200010];
vector<int>v[100010];//每块内的元素
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    for(int i=1;i<=n;i++)
        v[(i-1)/block+1].push_back(a[i]);
}
void rebuild()
{
    int tot=0;
    for(int i=1;i<=num;i++)
    {
        for(int j=0;j<v[i].size();j++)
            zs[++tot]=v[i][j];
        v[i].clear();
    }
    block=sqrt(tot);
    num=tot/block;if(tot%block)num++;
    for(int i=1;i<=tot;i++)
        v[(i-1)/block+1].push_back(zs[i]);
}
void update(int l,int r)//在l前面加入r
{
    for(int i=1;i<=num;i++)
    {
        int can=l-v[i].size();
        if(can>0)
            l=l-v[i].size();//x不在这块
        else
        {
            v[i].insert(v[i].begin()+l-1,r);
            if(v[i].size()>20*block)rebuild();
            /*for(int j=1;j<=num;j++)
            {
                for(int k=0;k<v[j].size();k++)
                    printf("%d ",v[j][k]);
                printf("\n");
            }*/
            break;
        }
    }
}
void ask(int x)
{
    for(int i=1;i<=num;i++)
    {
        int can=x-v[i].size();
        if(can>0)x=x-v[i].size();//x不在这块
        else
        {
            printf("%d\n",v[i][x-1]);
            //printf("v[%d]\n",i);
            return;
        }
    }
}
int main()
{
    //freopen("/Users/apple/Desktop/input.txt","r",stdin);
   //freopen("/Users/apple/Desktop/output.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build();
    int ope,l,r,c;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d%d",&ope,&l,&r,&c);
        if(ope==0)update(l,r);
        else if(ope==1)ask(r);
    }
    return 0;
}

LOJ 6283

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

思路：之前线段树专题里做过差不多的题目，lazy标记变成ax+b形式即可。这里每次更新a[i]，即块外的时候，要把标记下放，否则会打乱乘除的顺序，在块内则不需要，因为块内并没有改变a[i]，如果块内之后变成块外的话，会下放。

代码：

int n;
long long a[100010];
int num;//分块的个数
int belong[100010];//每个数属于哪个分块
int block;//每个块的大小
int lef[100010],rig[100010];//该块的左/右端点位置
long long d[100010][2];//每个块的增量ax+b
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
    {
        lef[i]=(i-1)*block+1,rig[i]=i*block;
        d[i][0]=1;d[i][1]=0;
    }
    rig[num]=n;//最后一块不满的情况
}
void pushdown(int x)
{
    for(int i=lef[x];i<=rig[x];i++)
    {
        a[i]=(a[i]*d[x][0])%MOD;
        a[i]=(a[i]+d[x][1])%MOD;
    }
    d[x][0]=1;d[x][1]=0;
}
void update1(int l,int r,long long c)
{
    if(belong[l]==belong[r])
    {
        if(d[belong[l]][0]!=1||d[belong[l]][1]!=0)pushdown(belong[l]);
        for(int i=l;i<=r;i++)
            a[i]=(a[i]+c)%MOD;
    }
    else
    {
        //printf("belong:%d %d\n",belong[l],belong[r]);
        if(d[belong[l]][0]!=1||d[belong[l]][1]!=0)pushdown(belong[l]);
        for(int i=l;i<=rig[belong[l]];i++)
            a[i]=(a[i]+c)%MOD;
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
            d[i][1]=(d[i][1]+c)%MOD;//a[i]没有改变，不需要pushdown
        if(d[belong[r]][0]!=1||d[belong[r]][1]!=0)pushdown(belong[r]);
        for(int i=lef[belong[r]];i<=r;i++)
            a[i]=(a[i]+c)%MOD;
    }
    /*for(int i=1;i<=n;i++)
        printf("%lld ",a[i]);
    printf("\n");*/
}
void update2(int l,int r,long long c)
{
    if(belong[l]==belong[r])
    {
        if(d[belong[l]][0]!=1||d[belong[l]][1]!=0)pushdown(belong[l]);
        for(int i=l;i<=r;i++)
            a[i]=(a[i]*c)%MOD;
    }
    else
    {
        //printf("belong:%d %d\n",belong[l],belong[r]);
        if(d[belong[l]][0]!=1||d[belong[l]][1]!=0)pushdown(belong[l]);
        for(int i=l;i<=rig[belong[l]];i++)
            a[i]=(a[i]*c)%MOD;
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
            d[i][0]=(d[i][0]*c)%MOD,d[i][1]=(d[i][1]*c)%MOD;
        if(d[belong[r]][0]!=1||d[belong[r]][1]!=0)pushdown(belong[r]);
        for(int i=lef[belong[r]];i<=r;i++)
            a[i]=(a[i]*c)%MOD;
    }
    /*for(int i=1;i<=n;i++)
        printf("%lld ",a[i]);
    printf("\n");*/
}
void ask(int r)
{
    long long ans=a[r];
    ans=(ans*d[belong[r]][0])%MOD;
    ans=(ans+d[belong[r]][1])%MOD;
    printf("%lld\n",ans);
}
int main()
{
    //freopen("/Users/apple/Desktop/input.txt","r",stdin);
    //freopen("/Users/apple/Desktop/output.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build();
    int ope,l,r;
    long long c;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d%lld",&ope,&l,&r,&c);
        if(ope==0)update1(l,r,c);
        else if(ope==1)update2(l,r,c);
        else if(ope==2)ask(r);
    }
    return 0;
}

LOJ 6284

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

思路：维护每个分块是否只有一种权值，区间操作的时候，对于同权值的一个块就O(1)统计答案，否则暴力统计答案，并修改标记，不完整的块也暴力。

假设初始序列都是同一个值，那么查询是O(√n)，如果这时进行一个区间操作，它最多破坏首尾2个块的标记，所以只能使后面的询问至多多2个块的暴力时间，所以均摊每次操作复杂度还是O(√n)。换句话说，要想让一个操作耗费O(n)的时间，要先花费√n个操作对数列进行修改。pushdown操作类似上题。

代码：

int n;
int a[100010];
int num;//分块的个数
int belong[100010];//每个数属于哪个分块
int block;//每个块的大小
int lef[100010],rig[100010];//该块的左/右端点位置
int same[100010];
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
        lef[i]=(i-1)*block+1,rig[i]=i*block;
    rig[num]=n;//最后一块不满的情况
}
void pushdown(int x)
{
    for(int i=lef[x];i<=rig[x];i++)
        a[i]=same[x];
    same[x]=-1;
}
void solve(int l,int r,int c)
{
    int ans=0;
    if(belong[l]==belong[r])
    {
        if(same[belong[l]]!=-1)pushdown(belong[l]);
        for(int i=l;i<=r;i++)
        {
            if(a[i]==c)ans++;
            else a[i]=c;
        }
    }
    else
    {
        if(same[belong[l]]!=-1)pushdown(belong[l]);
        for(int i=l;i<=rig[belong[l]];i++)
        {
            if(a[i]==c)ans++;
            else a[i]=c;
        }
        for(int i=belong[l]+1;i<=belong[r]-1;i++)
        {
            if(same[i]!=-1)
            {
                if(same[i]==c)ans+=block;
                else same[i]=c;
            }
            else//不同
            {
                for(int j=lef[i];j<=rig[i];j++)
                {
                    if(a[j]==c)ans++;
                    else a[j]=c;
                }
                same[i]=c;
            }
        }
        if(same[belong[r]]!=-1)pushdown(belong[r]);
        for(int i=lef[belong[r]];i<=r;i++)
        {
            if(a[i]==c)ans++;
            a[i]=c;
        }
    }
    printf("%d\n",ans);
}
int main()
{
    //freopen("/Users/apple/Desktop/input.txt","r",stdin);
    //freopen("/Users/apple/Desktop/output.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    memset(same,-1,sizeof(same));
    build();
    int l,r,c;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d",&l,&r,&c);
        solve(l,r,c);
    }
    return 0;
}

LOJ 6285

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

思路：

解法一：

众数应该是完整的所有块的众数，和不完整块中出现的数。

所以我们可以预处理f(i,j)表示第 i 块到第 j 块的众数（枚举 i 开个桶扫一遍）。

对于块内的众数就用预处理出来的；对于块外的，给每个数 x 开个vector，按顺序存下 x 出现的位置，每次询问 x 时把区间的左右端点放进对应 vector 二分一下即可。

为了不爆内存，所以要先离散化。

我第一次是直接用map映射，每次读取都是mp[a[i]]这样，结果TLE到怀疑人生。看了别人的代码，发现别人的map不是这样用的，而是开了val数组来保存离散后的编号所对应的原来的数字，然后把原数列变成离散后的样子。原来map这么慢啊…涨姿势…（其实还有一种离散的方式来着吧…

解法二：

查询之前，先预处理一下，统计出两个东西：cnt(i)(j)和ans(i)(j)。
cnt(i)(j)表示i这个数在前j块出现的次数；
ans(i)(j)表示从i块到j块的答案，统计的都是整块的答案。
搞定这些的时间复杂度是O(nn√)的。
对于cnt(i)(j)的统计，先做出每一块i出现的次数，然后一遍前缀和搞定。对于ans(i)(j)的统计，先确定起点l，就是第i块的起点，然后r向后暴力移动统计，当r等于一个块的终点时，记录答案。
对于统计ans(i)(j)时，别忘了清数组，看好r……

对于块外的，用前缀和处理，不够的地方暴力统计。

因为这里数据范围有1e5，cnt数组如果在块大为√n时会爆内存（看到最快的用这种方法100000*500居然没爆内存？？？我以为1e6就要爆内存了？？？（迷）），或许把块搞得大一点可以？

代码（解法一）：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int n;
int a[100010];
int num;//分块的个数
int belong[100010];//每个数属于哪个分块
int block;//每个块的大小
int lef[400],rig[400];//该块的左/右端点位置
int f[400][400];//第i块到第j块的众数
int ff[400][400];//第i块到第j块的众数出现的次数
map<int,int>mp;//离散数据
vector<int>v[100010];//记录每个数字（离散后）出现的位置
int val[100010];
int apr[100010];//每个数出现的次数（桶排）
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
        lef[i]=(i-1)*block+1,rig[i]=i*block;
    rig[num]=n;//最后一块不满的情况
}
void init()
{
    for(int i=1;i<=num;i++)
    {
        int MAX=0;//出现最多的数字出现的最多次数
        int pos=INF;//出现最多的数字
        memset(apr,0,sizeof(apr));
        for(int j=lef[i];j<=n;j++)
        {
            apr[a[j]]++;
            if(apr[a[j]]>MAX||(apr[a[j]]==MAX&&val[a[j]]<pos))//最小众数
                pos=val[a[j]],MAX=apr[a[j]],
                f[i][belong[j]]=pos,ff[i][belong[j]]=MAX;
        }
    }
    /*for(int i=1;i<=num;i++)
     for(int j=i;j<=num;j++)
     printf("%d~%d:%d %d\n",i,j,f[i][j],ff[i][j]);*/
}
void solve(int l,int r)
{
    int ans=INF,MAX=0;
    if(belong[l]==belong[r])
    {
        for(int i=l;i<=r;i++)
        {
            int d=upper_bound(v[a[i]].begin(),v[a[i]].end(),r)-lower_bound(v[a[i]].begin(),v[a[i]].end(),l);
            if(d>MAX||(d==MAX&&val[a[i]]<ans))
                ans=val[a[i]],MAX=d;
        }
    }
    else
    {
        ans=f[belong[l]+1][belong[r]-1];
        MAX=ff[belong[l]+1][belong[r]-1];
        for(int i=l;i<=rig[belong[l]];i++)
        {
            int d=upper_bound(v[a[i]].begin(),v[a[i]].end(),r)-lower_bound(v[a[i]].begin(),v[a[i]].end(),l);
            if(d>MAX||(d==MAX&&val[a[i]]<ans))
                ans=val[a[i]],MAX=d;
        }
        for(int i=lef[belong[r]];i<=r;i++)
        {
            int d=upper_bound(v[a[i]].begin(),v[a[i]].end(),r)-lower_bound(v[a[i]].begin(),v[a[i]].end(),l);
            if(d>MAX||(d==MAX&&val[a[i]]<ans))
                ans=val[a[i]],MAX=d;
        }
    }
    printf("%d\n",ans);
}
int main()
{
    //freopen("/Users/apple/Desktop/input.txt","r",stdin);
    //freopen("/Users/apple/Desktop/output.txt","w",stdout);
    scanf("%d",&n);
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(mp[a[i]]==0){mp[a[i]]=++cnt;val[cnt]=a[i];}//离散化
        a[i]=mp[a[i]];
        v[a[i]].push_back(i);
    }
    build();
    init();
    int l,r;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&l,&r);
        solve(l,r);
    }
    return 0;
}