块状数组

鸽了好多天，今天终于开始写了233...

分块思想

实际上分块并不能算一种数据结构？
分块的基本思想是，将原来的数据经过适当的划分(分成一个个块的样子)。
每次修改和询问时，都把一个块内元素当作整体处理，而边角直接暴力。
莫队就是基于分块思想实现的。

分块的复杂度主要取决于块长，根据均值不等式，块长为\(\mathjaxcal{O}(\sqrt n)\)时最优。当然不能一概而论。详细分析可以阅读\(2017\)年国家集训队论文中徐明宽的《非常规大小分块算法初探》。 所以分块的时间复杂度一般都是带根号的...

分块入门

基本操作

块大小：

size = sqrt(n - 1) + 1
```  
块个数:
```cpp
block = (n - 1) / size + 1

预处理每个块的区间和每个元素所在块编号：

for (int i = 1; i <= block; i++) {
    L[i] = R[i - 1] + 1;
    R[i] = i * blo;
}
R[block] = n;
for (int i = 1; i <= block; i++) {
    for (int j = L[i]; j <= R[i]; j++) bel[j] = i;
}
```  
### 入门例题
先看看两道入门题...  
#### [LOJ 6280 入门分块4](https://loj.ac/problem/6280)  
若$opt=0$，表示将位于$[l,r]$的之间的数字都加$c$。
若$opt=1$，表示询问位于$[l,r]$的所有数字的和$\bmod (c+1)$。  

这道题看起来是线段树的模板题，~~实际上就是~~。  
做法不难想到，分好块以后，给每个块记录一个$tag$和$sum$。  
$tag$表示这个块的所有元素都要加多少，相当于线段树里面的懒标记。 
每次操作，$[l,r]$中完整块都可以$\mathjaxcal{O}(1)$做，而边角的元素一个一个去加或者统计就可以了。  
因为只有$\mathjaxcal{O}(\sqrt n)$个块，边角的元素个数也是$\mathjaxcal{O}(\sqrt n)$。  
所以总的时间复杂度是$\mathjaxcal{O}(\sqrt n)$。  

为了方便理解，放一下修改的代码。  
```cpp
void upd(int l, int r, int v) {
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i++) a[i] += v, sum[bel[i]] += v;;
    } else {
        for (int i = l; i <= R[bel[l]]; i++) a[i] += v, sum[bel[i]] += v;
        for (int i = L[bel[r]]; i <= r; i++) a[i] += v, sum[bel[i]] += v;
        for (int i = bel[l] + 1; i < bel[r]; i++) tag[i] += v;
    }
}

LOJ 6280 入门分块6

给出一个长为\(n\)的数列，以及\(n\)个操作，操作涉及单点插入，单点询问，数据随机生成。
若\(opt=0\)，表示在第\(l\)个数字前插入数字 \(r\)（ 忽略）。 若\(opt=1\)，表示询问\(a-r\)的值。 先说数据随机怎么做。
把块分好之后，每个块里面都可以存一个动态数组。
每次插入，只需要找到\(l\)所在的块，在\(vector\)里面直接插入新的数就可以了。时间复杂度\(\mathjaxcal{O}(\sqrt n)\)。
查询，也只需要找到位置输出就可以了。

构造数据？
可能会有毒瘤数据将所有的插入都差到一个块里面，那么上面的做法就会被卡飞...
那怎么办呢？
既然有一个块太大了，那把它变小就可以了...
重构所有块有两种时机:
1. 操作的时候发现某些块太大，就直接重构后操作。
2. 隔一段时间进行重构，比如\(\mathjaxcal{O}(\sqrt n)\)次，每次重构是\(\mathjaxcal{O}(n)\)的，总时间复杂度是\(\mathjaxcal{O}(n\sqrt n)\)。

LOJ6285 入门分块9也是道很好的的题。值得做做

一些例题

P2801 教主的魔法

（1） 若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。 （2） 若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。

这次分块的时候需要把每个块的元素存下来。

size = sqrt(n);
for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    block[tot][++block[tot][0]] = a[i];
    if (block[tot][0] == size)
        tot++;
}

对每个块进行排序。
第二个操作可以对每个有序的块\(lower\-bound\)一下就可以了。
怎么修改？
整块打上懒标记就可以了。
边角的每个元素，都去找到对应块中的元素，然后直接加就可以了。
时间复杂度显然是\(\mathjaxcal{O}(n\sqrt n log n)\)。

P5048 [Ynoi2019模拟赛]Yuno loves sqrt technology III

给你一个长为 \(n\)的序列 \(a\)，\(m\) 次询问，每次查询一个区间的众数的出现次数，强制在线。

发现值域比较小，先把所有元素放入按权值放入桶中，并且记录下在桶里面的下标。
之后考虑整块的怎么做。
可以暴力\(dp\)，设\(f_{l,r}\)表示第\(l\)块到\(r\)块的众数出现次数。

for (int i = 1; i <= block; i++) {
    memset(tot, 0, sizeof tot);
    for (int j = L[i]; j <= R[i]; j++) bel[j] = i;
    for (int j = i;j <= block; j++) {
        mx[i][j] = mx[i][j - 1];
        for (int k = L[j]; k <= R[j]; k++) mx[i][j] = max(mx[i][j], ++tot[a[k]]);
    }
}

之后每次查询，只用考虑边角元素的贡献。
记现在已经可能的答案是\(ans\)，只用检验会不会有数出现次数是\(ans+1\)。
对于左边的元素，假设它在桶中的位置是\(pos\)，如果\(v[a][pos+ans]\leq r\)，说明它是可以成为目前众数的，所以\(ans=ans+1\)。 右边同理。
因为答案最多加\(\mathjaxcal{O}(\sqrt n)\)次，所以复杂度是\(\mathjaxcal{O}(m\sqrt n)\)。

P4117 [Ynoi2018]五彩斑斓的世界

最后一道题了...

1. 把区间\([l,r]\)中大于\(x\)的数减去\(x\)。
2. 查询区间\([l,r]\)中\(x\)的出现次数。

看了出题人的题解才会做...
分块，可以发现每块的最大值总是不增的。
1. 若 \(2x\geq k\)，令大于 \(x\) 的数减去 \(x\) 之后，就没有比 \(x\) 大的数了，则 \(k\) 在操作后至少减少 \(k-x\)。
2. 若 \(2x\lt k\)，则我们令小于等于 \(x\) 的数加上 \(x\)，就没有比 \(x\) 小的数了，然后。打全局减的标记，则 \(k\) 在操作后至少减少 \(x\)。

使用并查集把相同的值并起来。那么修改的时候，只需要把修改前值对应的并查集的根，连到修改后的值的并查集的根上即可。
同时我们需要记录每个数的出现次数，修改的时候直接加过去就好了。

我们每次用来连接的都是并查集的根，而一个根连到另一个根之后，这个值本身就消失了。而且我们在这里并不用这个并查集查询。因此这里的并查集并不会进行路径压缩，是 \(\mathjaxcal{O}(1)\) 的。
如果是查询全局某个数的出现位置，那么直接\(\mathjaxcal{O}(1)\)查询即可。 我们考虑查询所有位置的实际值。这里就需要用到并查集的找父亲的操作了。由于这里访问了并查集的所有位置，并进行了路径压缩，所以总复杂度是\(\mathjaxcal{O}(n)\)的。

所以对一个整块的修改查询都是\(\mathjaxcal{O}(n\sqrt n)\)的。 对于一个块的部分修改，我们先暴力把每个位置的实际值还原，然后对块进行重构即可。\(\mathjaxcal{O}(\sqrt n)\)。

如果所有数都开一个并查集的话，空间复杂度显然是不能接受的...
发现块与块之间的操作是独立的，所以可以把操作离线下来。
每个块都单独做完所有操作后统计答案。