P1822题解， 分块与打表的有机结合

· · 题解

免责声明：我不是来讲正解的，这是写给OI入门学者们的分块题解

内容较水，有错误欢迎直接D

分块基础

分块是一种优美的暴力。他的核心思想在于将一个要维护的区间（长度为 n）分成有穷个 \sqrt n 个子区间来进行分别维护。每个子区间的长度都为 \sqrt n。

我们所要查询的区间所覆盖的每个块的信息进行整合，就是我们要查询的区间的信息。

这样将区间分块来处理有什么好处呢？可以感性理解，如果我们已经有了这个块的全部信息，那么下一次要查询包含这个块的区间信息时，就直接调用这个块就可以了。显然优化了不少。

分块区间构造起来思维难度不高，我们直接在代码中的注释进行讲解和理解。

int S,C=0,belong[500010],st[10010],en[10010],sum[10010]={0};

S代表每个块的长度，即为根号n取整。
C代表所分成的块的个数，一般也是根号n取整
belong[i]代表原区间中的第 i 个元素所属块的编号
st[i] 表示第 i 个块的左端点，同理 en[i] 代表右端点
sum[i] 代表第i个块元素信息的整合，对于这里的代码展现我使用的是和的形式

inline void build()
{
   S=int(sqrt(double(n)));  //求出S的大小
   for(register int i=1;i<=n;i+=S)  //为每个块设立左端点和右端点
   {
      st[++C]=i;
      en[C]=min(n,i+S-1);
   }
   for(register int i=1;i<=C;++i)  //枚举所有的块
   {
     for(register int j=st[i];j<=en[i];++j)  //遍历每个块中的元素，将他们所属的块的编号记录
     {
       belong[j]=i;  //表示第j个元素是第i块的
       sum[i]+=a[j];  //统计第i块元素的和
     }
   }
   return ;
}

显而易见，只有此元素所在的块才会因为单点修改而产生改变，因此直接修改就好了。

inline void single(int x,int k)  在第x个位置加上k
{
  a[x]+=k;
  sum[belong[x]]+=k;   //在x所属块的信息集合sum数组中进行修改
  return ;
}

我们使用一个数组 delta ，delta_i 记录第 i 个块 整个块被修改的变化情况，当且仅当这个块被整块一起修改的时候，才会改变这个块的 delta。

设要修改的区间的左端点是 l，右端点是 r，若 [l,r] 的位置和我们已分好的一个块重合：

\boxed{~~~~~~~~~~~~~}\quad\boxed{~~~~~~~~~~~~~}\quad\boxed{~~~~~~~~~~~~~}\quad\boxed{~~~~~~~~~~~~~}\quad\boxed{~~~~~~~~~~~~~} \colorbox{Black}{~~~~~~~~~~~~~}

ps:白色块为所分的块，黑色块为[l,r]

也就是说存在第 i 个块使得 st_i=x且en_i=y，那么我们可以对这个块进行整块操作，即直接改变 delta_i 的值。

  int l=belong[x],r=belong[y];
  if(l==r&&st[l]==x&&en[l]==y)
  {
    delta[l]+=k;  //记录第 l 个块的变化情况。
    return ;
  }

可是，要是 x,y 并不是理想的刚好在一个块中，而是同时涉猎了三个块呢？

\boxed{~~~~~~~~~~~~~}\,\boxed{~~~~~~~~~~~~~}\,\boxed{~~~~~~~~~~~~~}\,\boxed{~~~~~~~~~~~~~}\,\boxed{~~~~~~~~~~~~~} \colorbox{Black}{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}

很简单，对于 [l,r] 区间内，那些完整的块我们通过改变 delta 来改变，而那些不完整的块，我们通过单点修改 single 来一一改变他们的原值。

  for(register int i=x;i<=en[l];++i)  //改变左边的不完整区间
    single(i,k);
  for(register int i=st[r];i<=y;++i)  //改变右边的不完整区间
    single(i,k);
  for(register int i=l+1;i<r;++i)  //完整区间统一修改
    delta[i]+=k;

因此一个完整的区间修改函数 range 就出来了

int delta[10010]={0};
inline void range(int x,int y,int k)
{
  int l=belong[x],r=belong[y];
  if(l==r&&st[l]==x&&en[l]==y)
  {
    delta[l]+=k;
    return ;
  }
  for(register int i=x;i<=en[l];++i)
    single(i,k);
  for(register int i=st[r];i<=y;++i)
    single(i,k);
  for(register int i=l+1;i<r;++i)
    delta[i]+=k;
  return ;
}

仍然考虑查询一个 [l,r] 的区间，如果 l,r 在同一个块内，那么也许会是这么一种情况：

\boxed{~~~~~~~~~~~~~}\quad\boxed{~~~~~~~~~~~~~}\quad\boxed{~~~~~~~~~~~~~}\quad\boxed{~~~~~~~~~~~~~}\quad\boxed{~~~~~~~~~~~~~} \colorbox{Black}{~~~}

此时，[l,r] 的确在一个块内，但是又并不是占据这整一个块，这种情况我们就需要特判处理

  int l=belong[x],r=belong[y],ans=0;
  if(l==r)
  {
    for(register int i=x;i<=y;++i)
      ans+=a[i]+delta[belong[i]];  //最朴素的对该区间进行求和，此时delta数组就派上用场了。
    return ans;
  }

对于区间查询，我们依旧可以尝试像区间修改那样思考，将区间所占据的块分为三部分：

  1. 左边的不完整块
  2. 中间的完整块
  3. 右边的不完整块。

这样我们就可对区间进行有逻辑的查询。

对于左右不分，直接暴力处理即可，对于中间完整块，信息整合数组sum和变化记录数组delta的功能就体现出来了，他们极大程度的优化了完整块的处理。

  for(register int i=x;i<=en[l];++i)  //左半不完整部分
    ans+=a[i]+delta[belong[i]];
  for(register int i=st[r];i<=y;++i)  //右半不完整部分
    ans+=a[i]+delta[belong[i]];
  for(register int i=l+1;i<r;++i)  //完整的块直接利用sum和delta卡速累加即可
    ans+=sum[i]+delta[i]*(en[i]-st[i]+1);

这样就是一个完整的分块区间查询函数：

inline int query(int x,int y)
{
  int l=belong[x],r=belong[y],ans=0;
  if(l==r)
  {
    for(register int i=x;i<=y;++i)
      ans+=a[i]+delta[belong[i]];
    return ans;
  }
  for(register int i=x;i<=en[l];++i)
    ans+=a[i]+delta[belong[i]];
  for(register int i=st[r];i<=y;++i)
    ans+=a[i]+delta[belong[i]];
  for(register int i=l+1;i<r;++i)
    ans+=sum[i]+delta[i]*(en[i]-st[i]+1);
  return ans;
}

分块打表

相信此时的你已经对分块有了基础的认识，那么我们回到这道题目，如何利用分块来暴力解决呢？

如果你不会省选级别思维难度的搜索，那么在考场自然而然的思路就是打表。

但是很显然，这题的数据规模直接打表的话会爆程序长度，那么怎么办？限制打表的不是程序，而是人心。 我们可以选择分块打表

分块打表的思路和分块简直如出一辙：我们直接线下求出每一个块的信息整合，也就是对于每个块进行打表，然后利用分块来合并信息。

思路非常清晰，对于这题，我们可以将每个块的长度设为1000000，然后打表求得每个块的幸运数个数，然后利用分块算法流程来对所查询区间进行信息整合。

先奉上打表程序：

int n,tot=0,sum[1000010]={0};
int magic(int x)
{
    if(x<10) return x;
    int a[20],t=0;
    while(x)
    {
        a[++t]=x%10;
        x/=10;
    }
    int m=0;
    for(int i=t;i>=2;i--)
    {
        m=m*10+abs(a[i]-a[i-1]);
    }
    return magic(m);
}
int main()
{
    cin>>n;
    tot=1;
    for(int i=1;i<=n;i++)
    {
        if(i%1000000==0) sum[tot]+=sum[tot-1],tot++;
        sum[tot]+=(magic(i)==7);
    }
    for(int i=1;i<=tot;i++)
      {
        if(sum[i]==0) break;
        cout<<sum[i]<<',';
      }
    return 0;
}

对于这段程序输出的是每一个长度为 1000000 的块所含幸运数的前缀和。

有了打表的帮助，我们就等于有了每个块的信息（利用前缀和相减求区间和总会吧），然后直接如上文所讲利用这些块进行分块中的区间信息整合即可。

CODE:

#include <bits/stdc++.h>
using namespace std;
int sum[1010]={//已删减};
int st[1010],en[1010],S,tot;
int l,r;
int belong(int x)  //求当前元素所属块的编号
{
    if(x%1000000==0) return x/1000001+1;
    else return x/1000000+1;
}
void start()
{
  S=1000000;
  for(int i=1;i<=r;i+=S)
  {
    st[++tot]=i;
    en[tot]=i+S-1;
  }
  return ;
  //预处理块的左右端点
}
int magic(int x)  //求得magic值（本人蒟蒻，写得特别丑）
{
    if(x<10) return x;
    int a[20],t=0;
    while(x)
    {
        a[++t]=x%10;
        x/=10;
    }
    int m=0;
    for(int i=t;i>=2;i--)
    {
        m=m*10+abs(a[i]-a[i-1]);
    }
    return magic(m);
}
int range(int l,int r)  //分块思路的区间查询
{
  int ans=0;
  if(belong(l)==belong(r))
  {
    for(int i=l;i<=r;i++)
      ans+=(magic(i)==7);
    return ans;
  }
  ans=sum[belong(r)]-sum[belong(l)-1];
  for(int i=st[belong(l)];i<l;i++)
    ans-=(magic(i)==7);
  for(int i=r+1;i<=en[belong(r)];i++)
    ans-=(magic(i)==7);
  return ans;
}
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>l>>r;
  start();
  cout<<range(l,r);
  return 0;
}

总结

这是蒟蒻的第一篇博客，望能通过本人的一点点微微的帮助，使得更多人在偶然中体会算法之美。