【题解】教主的魔法

洛谷博客欢迎来踩。

摘要

分块，是一种优雅的暴力，它通过对数列分段，完成对数列一些区间操作和区间查询的操作，是一种根号算法。

这篇学习笔记&题解是本萌新在学习分块过程中的一些感悟，希望能够帮助分块零基础的同学学会基础分块。

0 说明

本文中，以下变量有特定的含义：

$block$ ：块的大小
$n$ ：被分块的数列的大小（长度）
$L_{x}$ ：第 $x$ 号块的左边界
$R_{x}$ ：第 $x$ 号块的右边界
$tot$ ：块的数量
$belong_{x}$ ：第 $x$ 号元素所属的块

在写作时，由于本萌新的失误，只好提前在这里令 $[l,r]$ 与 $[x,y]$ 等价。

1 建块

1.1 建块需要完成的任务

在读入数据后，建块需要完成以下几个任务：

确定块的大小
确定块的数量
标记每个块的左右边界
标记每个元素所属的块
对每个块的数据进行初始化

1.2 确定块的大小

一般来说，我们习惯于令$ $block=\sqrt{n}$ $

但是由于毒瘤良心命题人泛滥， $block=\sqrt{n}$ 极其有可能被针对，在这种情况下，我们可以对块的大小适当作出一些调整，例如 $\sqrt{n}+1$ ， $\sqrt{n}-1$ ， $\sqrt{\frac{n}{lg(n)}}$ 等。

一般这个工作只有一句话：

block=sqrt(n);

1.3 确定块的数量

在确定了块的大小后，块的数目就很容易确定了。

但是 $n$ 不一定是一个完全平方数，我们需要把最后几个无法凑足 $block$ 个元素的再单独分一个块。

代码如下：

tot=n/block;
if(n%block)
    tot++;

1.4 标记每个块的左右边界

非常显然， $L_1=1,R_1=block,L_2=block+1,R_2=2×block...$

从而可以得出结论：$ $L_{x}=(x-1)×block+1$ $$ $R_{x}=x×block$ $

特别地， $R_{tot}=n$

代码：

for(int i=1;i<=tot;i++){
    L[i]=(i-1)*block+1;
    R[i]=i*block;
}
R[tot]=n;

1.5 标记每个元素所属的块

根据1.4，我们很容易推出公式如下：

$belong_{x}=\frac{x-1}{block}+1$

代码如下：

for(int i=1;i<=n;i++)
    belong[i]=(i-1)/block;

重要：在使用分块过程中，一定要小心 $tot$ 和 $n$ 的书写错误~~不能出现重大审题性错误~~@朱卫红

1.6 对每个块的元素进行初始化

这项工作因题目不同而不同，如【教主的魔法】一题，就要对每个块的元素进行排序。

因为排序会对原始数列作出改变，所以在本题中，应当先把数列复制一遍再进行分块

2 分块题常见的操作

修改：

对数列 $[l,r]$ 内的每个数加上 $k$
对数列 $[l,r]$ 内的每个数减去 $k$
etc.

查询：

求数列 $[l,r]$ 内的所有数的和
求数列 $[l,r]$ 内的数有多少大于/小于/大于等于/小于等于 $k$
etc.

3 修改操作

考虑两种修改操作本质相同，第二种修改操作相当于第一种修改操作中 $k=-k'$ 。

3.1 暴力修改

考虑枚举区间 $[l,r]$ 之间所有数，直接对其实施修改，在修改的过程中维护每一个块的和/大小关系等。

但这不是我们考虑的东西

3.2 考虑线段树思想

线段树一个重要思想： $lazytag$

考虑应用在分块中。在修改操作中，如果是整块，就不维护每个的具体信息，而是在这个块的 $lazy$ 标记上加上 $k$ 。对于没有整块修改的部分（即块 $belong_x$ 和 $belong_y$ 的修改部分），暴力修改。

这样的话，第 $i$ 个数据 $a_i$ 的真正数据值 $=a_i+lazy_{belong_{i}}$

如果询问涉及到排序，块 $belong_x$ 和 $belong_y$ 需要全部重新备份和排序，对于块 $[belong_x+1,belong_y-1]$ 的块，数的相对大小不会改变，所以可以不重新排序。

特别地，需要特判 $belong_x=belong_y$ 的情况。

代码：

void change(){
    if(belong[x]==belong[y]){
        for(int i=x;i<=y;i++){
            a[i]+=k;
            sum[belong[x]]+=k;
        }
        return;
    }
    for(int i=x;i<=R[belong[x]];i++){
        a[i]+=k;sum[belong[x]]+=k;
    }
    for(int i=L[belong[y]];i<=y;i++){
        a[i]+=k;sum[belong[y]]+=k;
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++){
        lazy[i]+=k;
        sum[i]+=blo*k;
    }
}

对以下这句代码作出特别解释：

sum[i]+=blo*k;

不用特判最后一块的原因是：如果操作区间覆盖到的最后一块，也一定是作为 $belong_y$ 处理掉了，剩下来的块长一定是 $block$ 。

4 查询操作

4.1 查询元素和

对于块 $belong_x$ 和 $belong_y$ ，暴力枚举加和，注意加上其元素后还要加上 $lazy_{belong_{i}}$

对于 $[belong_x+1,belong_y-1]$ 的块，直接 $ans=ans+sum_i$ 即可。

同样的，需要特判 $belong_l=belong_r$

代码：

int query_sum(){
    int ans=0;
    if(belong[x]==belong[y]){
        for(int i=x;i<=y;i++){
            ans+=a[i]+lazy[belong[x]];
        }
        return ans;
    }
    for(int i=x;i<=R[belong[x]];i++){
        ans+=a[i]+lazy[belong[x]];
    }
    for(int i=L[belong[x]];i<=y;i++){
        ans+=a[i]+lazy[belong[y]];
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++){
        ans+=sum[i];
    }
    return ans;
}

4.2 查询关系

与4.1类似，在块 $belong_x$ 和 $belong_y$ ，暴力枚举求答案；

对于[belong_x+1,belong_y-1]的块，因为其是有序的，进行二分找到端点位置，然后加加减减求出块中有多少符合要求的元素即可。

本处代码见5.

5 教主的魔法

在学习完分块后，我们可以发现，教主的魔法就是一道裸的分块题。

因此，完整代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[1000007],d[1000007],L[1007],R[1007],belong[10000007],lazy[1007],ans;
int n,q,block,tot,x,y,k;
char cz;
template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')){
        ch=getchar();
    }
    if(ch=='-'){
        fh=-1;ch=getchar();
    }else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    x*=fh;
}
void fr(char &x)
{
    x=0;while(x!='M'&&x!='A') x=getchar();
}
void build()
{
    block=sqrt(n);tot=n/block;
    if(n%block) tot++;
    for(register int i=1;i<=n;i++){
        belong[i]=(i-1)/block+1;d[i]=a[i];
    }
    for(register int i=1;i<=tot;i++){
        L[i]=(i-1)*block+1,R[i]=i*block;
    }
    R[tot]=n;
    for(register int i=1;i<=tot;i++){
        sort(d+L[i],d+R[i]+1);
    }
}
void change()
{
    if(belong[x]==belong[y]){
        for(register int i=x;i<=y;i++){
            a[i]+=k;
        }
        for(register int i=L[belong[x]];i<=R[belong[x]];i++){
            d[i]=a[i];
        }
        sort(d+L[belong[x]],d+R[belong[x]]+1);
    }
    else{
        for(register int i=x;i<=R[belong[x]];i++){
            a[i]+=k;
        }
        for(register int i=L[belong[x]];i<=R[belong[x]];i++){
            d[i]=a[i];
        }
        sort(d+L[belong[x]],d+R[belong[x]]+1);
        for(register int i=L[belong[y]];i<=y;i++){
            a[i]+=k;
        }
        for(register int i=L[belong[y]];i<=R[belong[y]];i++){
            d[i]=a[i];
        }
        sort(d+L[belong[y]],d+R[belong[y]]+1);
        for(register int i=belong[x]+1;i<=belong[y]-1;i++){
            lazy[i]+=k;
        }
    }
}
void query()
{
    ans=0;
    if(belong[x]==belong[y]){
        for(register int i=x;i<=y;i++){
            if(lazy[belong[x]]+a[i]>=k) ans++;
        }
        printf("%d\n",ans);
        return;
    }
    else{
        for(register int i=x;i<=R[belong[x]];i++){
            if(lazy[belong[x]]+a[i]>=k) ans++;
        }
        for(register int i=L[belong[y]];i<=y;i++){
            if(lazy[belong[y]]+a[i]>=k) ans++;
        }
        for(register int i=belong[x]+1;i<=belong[y]-1;i++){
            int ll=L[i],rr=R[i],result=0,mid;
            while(ll<=rr)
            {
                mid=(ll+rr)>>1;
                if(d[mid]+lazy[i]>=k)
                    rr=mid-1,result=R[i]-mid+1;
                else
                    ll=mid+1;
            }
            ans+=result;
        }
        printf("%d\n",ans);
    }
}
int mian()
{
    read(n);read(q);
    for(register int i=1;i<=n;i++)
        read(a[i]);
    build();
    while(q--){
        fr(cz);
        read(x);read(y);read(k);
        if(cz=='M'){
            change();
        }
        if(cz=='A'){
            query();
        }
    }
    return 0;
}

6 附

因为本人是个萌新，文字未免有些疏漏，欢迎大佬指导。