2020-01-22 分块

数组分块入门解题报告

——2020年1月21日

注：有部分文字和内容借用自mofish

一、关于分块

     *
   / | \
   * * *
 /|\/|\/|\
* * * * * *
 /|\ /|
 ........

不难看出它大概有层（最下面个数的话），所以进行修改、询问是级别的。分块本质上是只有 3 层的树，它只有大块大块和大块里面的小块组成：

中间的就是大块，为了保证时间、空间复杂度最优（像 zjy 说的那样），我们分成块。这些只需要了解就好了，下面就是对分块的理解。理解是说不对着、记着任何代码，可独立敲出来分块，并且能举一反三的那种。

比如说现在 10 个数，我们会把它分成 4 块：

OOO | OOO | OOO | O ^ pos[]

多出的那一块是角块，也就是不为 0，需要块数+1的情况。不用像 zjy 那样很麻烦的弄分好块，你假设每一大块用 pos[] 来表示，pos[x] = wei_zhi 就表示第个数在哪个块里。

然后上面就是 pos[1] = pos[2] = pos[3] = 1（前三个数分成一个块

pos[4] = pos[5] = pos[6] = 2

pos[7] = pos[8] = pos[9] = 3

pos[10] = 4（单独在一个块）

这个很好懂对吧，可我们咋搞 pos[x] = pos，让程序把 n 个数分好块呢？我们知道 C++ 的 / 是整除，现在我们，那么 4/3 = 5/3 = 1。也就是说，我们把 x/size + 1 就得到 x 所在的块。可这样有问题鸭，当 x=6 本来是刚刚好在第二块的，+1就变了，该死的整除 6/3=2。这也好办，防止倍数干扰，我们把 x 统统减一，让它不是 size 的倍数就好。也就是 pos[x] = (x - 1) / size + 1;。可以再体会一下防止整除就-1的思路。那么以忠诚2为例，我写的 pos[] 就是这样的意思。然后，用 minn[] 表示****每一块的最小值****，minn[pos[i]] 表示第 pos[i] 块的最小值是吧。那它就是在这个 pos 块内的 a[i] 的最小值嘛。我一开始把 minn[] 里面设的很大，然后直接和取 min 嘛。

1.png

2.png

3.png

4.png

分块实现如下：

for(int i=1; i<=n; i++)
    a[i]=read();
    for(int i=1; i<=n; i++)
        pos[i]=(i-1)/Count+1;

二、数列分块入门2

这个题一共涉及到两种操作， $Update$ 和 $Query$

同理，更新也是一样，对于角块而言，暴力更新的值，对于整块而言，将更新的值保存在中即可。这题我用 vecto r做的容器（相当于一个二维数组，每一维中都保存者当前块内元素信息~~不知道 sort 和 lower_bound 可以用于普通数组中~~），因而每次更新后还要将 Vector 重置（不重置直接加会炸空间）。

于是就有了这段代码：

void reset(int Pos)
{
     v[Pos].clear();
     for(int i=(Pos-1)*Count+1; i<=Pos*Count; i++)
     v[Pos].push_back(a[i]);
     sort(v[Pos].begin(),v[Pos].end());
}
void update(int l,int r,int c)
{
     for(int i=l; i<=min(r,pos[l]*Count); i++)
     a[i]+=c;
     reset(pos[l]);
     if(pos[l]!=pos[r])
     {
         for(int i=(pos[r]-1)*Count+1; i<=r; i++)
         a[i]+=c;
         reset(pos[r]);
     }
     for (int i =pos[l]+1; i <=pos[r]-1 ; i++)
         delay[i]+=c;
}

（~~后来交上去发现STL的速度真心慢……~~）

至于查找吗，思想是一样的，对于角块，暴力搜索查找，对于整块，在v[i]内二分查找（别忘了还有懒惰值）

代码实现如下

int Find(int l,int r,int c)
{
 int ans=0;
 for (int i=l; i<=min(pos[l]*Count,r); i++)
     if(a[i]+delay[pos[l]]<c)ans++;
 if(pos[l]!=pos[r])
     for (int i=(pos[r]-1)*Count+1; i<=r; i++)
 if(a[i]+delay[pos[r]]<c)ans++;
     for (int i = pos[l] + 1; i <=pos[r]-1; i++)
         ans+=lower_bound(v[i].begin(),v[i].end(),c-delay[i])-v[i].begin();
 return ans;
}

按理说分块大小（应为本段代码中的），然后TLE；但用48就不会（我也不清楚）。

故具体实现：（见DOJ）

最后编辑于：2020.01.23 18:53:11