谈到分块，不得不说说 $\text{hzwer}$ 学长的「数列分块入门」系列。
若未特别指出$\text{ML}$或$\text{TL}$，则$\text{ML:256MB,TL:500ms}$。
数列分块入门 1
题意
给出一个长为$n$的数列，有$n$个操作，操作涉及区间加法，单点查值。
$1\leq l\leq r\leq n\leq 50000$，输入的所有数均为$\text{int}$范围的整数。
$\text{TL:100ms}$
思路
啥？这题还要思路？
代码
1 |
|
数列分块入门 2
题意
给出一个长度为$n$的数列，以及$n$个操作，操作涉及区间加法，询问区间内小于某个值$x$的元素个数。
$1\leq l\leq r\leq n\leq 50000$，输入的所有数均为$\text{int}$范围的整数。
思路
将数列分成长为$S$的块。
修改就对整块打$\text{tag}$，对不完整的块暴力修改、排序，复杂度$O(\lfloor\frac{n}{S}\rfloor+S\log_2S)$。
询问就对整块$\text{lower_bound}$，对不完整的块暴力，复杂度$O(\lfloor\frac{n}{S}\rfloor\log_2S+S)$。
然后平衡一下，$S$ 取$\sqrt{n}$就好了。
代码
1 |
|
数列分块入门 3
题意
给出一个长为$n$的数列，以及$n$个操作，操作涉及区间加法，询问区间内$x$的前驱。
$1\leq l\leq r\leq n\leq 100000$，输入的所有数均为$\text{int}$范围的整数。
$\text{TL:1500ms}$
思路
基本同上「数列分块入门 2」，但是不能直接排序（复杂度$O(n\sqrt{n}\log_2n)$）而是需要用一些数据结构存储每个块的信息。
本人代码使用$set$存储每个块的信息。
微妙地调整块大小应该可以过吧……本人代码采用的是$S=n^{0.612}$
代码
1 |
|
数列分块入门 4
题意
给出一个长为$n$的数列，以及$n$个操作，操作涉及区间加法，区间求和并对$c$取模(每个询问给出)。
$1\leq l\leq r\leq n\leq 50000,c>0$,输入的所有数均为$\text{int}$范围的整数。
思路
经典问题，经典中的经典。
代码
1 |
|
数列分块入门 5
题意
给出一个长为$n$的数列，以及$n$个操作，操作涉及区间开方，区间求和。
$1\leq l\leq r\leq n\leq 50000$,输入的所有数均为$\text{int}$范围的自然数。
思路
什么这不是线段树题吗
代码
只写了线段树的代码，就不放了……
数列分块入门 6
题意
给出一个长度为$n$的数列，以及$n$个操作，操作涉及单点插入，单点查询。
$1\leq l\leq r\leq n\leq 100000$,输入的所有数均为$\text{int}$范围的整数。
第一行，一个数字$n$。
第二行$n$个数字，第$i$个数字为$a_i$。
接下来$n$行操作，每组操作输入四个数字$opt,l,r,c$。
若$opt=0$，表示在第$l$个数字前插入数字$r$。
若$opt=1$，表示询问$a_r$的值。
对每组$opt=1$的询问，输出一行一个整数，为$a_r$的值。
什么？你问我c干啥用的？我也想知道
思路
先把原序列分块，块大小$S$，块数$Bl$。
使用$\text{vector}$存储每一块信息。插入时暴力插入，将该块后面的元素都后移一位，复杂度$O(S)$；查询也是暴力，复杂度$O(Bl)$。
但是可能在一个块里有大量插入，此时该块大小将远远超过$S$，复杂度退化。
可以当某个块过大时，将该块分为两个，暴力重构，时间复杂度$O(n)$（若使用链表，可以锐减至$O(S+Bl)$。）
也可以考虑每$m$次插入后对序列进行重构，复杂度也为$O(n)$。
喂这种要”保持平衡”的思想不是和平衡树差不多吗你怎么不写棵平衡树
代码
本人采用的是$S=\sqrt{n}$，在块大小不小于$2S$时将该块分为两个，暴力拆块，复杂度$O(n)$。
由于最多只会拆$\sqrt{n}$次块，拆块复杂度$O(n\sqrt{n})$，可以通过此题。
1 |
|
数列分块入门 7
题意
给出一个长为$n$的数列，以及$n$操作，操作涉及区间加法，区间乘法，单点询问。
$1\leq l\leq r\leq n\leq 100000$,输入的所有数均为$\text{int}$范围的整数，询问对$10007$取模。
所以为什么不是查询区间和
思路
右转线段树模板，请
反正分块的思路基本相同，只是tag不用下传
代码
只写了线段树，所以不贴了。
数列分块入门 8
题意
给出一个长为$n$的数列，以及$n$个操作，操作涉及区间询问等于一个数 的元素，并将这个区间的所有元素改为$c$。
$1\leq l\leq r\leq n\leq 100000$,输入的所有数均为$\text{int}$范围的整数。
第一行，一个数字$n$。
第二行，$n$个数字，第$i$个为$a_i$。
接下来输入$n$行询问，每行三个数字$l,r,c$。
表示先查询位于$[l,r]$的数字有多少个是$c$，再将$[l,r]$内的数字都改为$c$。
数据不随机。
思路
分块，块大小$\sqrt{n}$，每块记录一下是否全部相等，若是则$O(1)$处理，不是则暴力扫一遍。不完整的块也暴力处理。
这样复杂度看上去最坏是$O(n)$的。然而，当经过了一次$O(n)$的询问后，几乎所有块都变得相等了。而一次操作最多将$2$个块变得不等，所以至少需要$\sqrt{n}$次操作后才可能再次出现$O(n)$的最坏复杂度。综合一下，可得复杂度是$O(n\sqrt{n})$，可以通过此题。
本人的说法可能不够严谨，希望有人可以提供更好的解释方法！
代码
1 |
|
加强
啊说起来本题还可以加强的来着。
给出一个长为$n$的数列，以及$n$个操作，操作涉及区间询问等于一个数 的元素，或将这个区间的所有元素改为$c$。
第一行，一个整数$n$。
第二行，$n$个整数，第$i$个为$a_i$。
接下来输入$n$行询问，每行四个整数$opt,l,r,c$。
若$opt=0$，表示将$[l,r]$内的所有数改为$c$。
若$opt=1$，输出一行一个整数，表示$[l,r]$内有多少个数是$c$。
数据不随机。
- $1\leq l\leq r\leq n\leq 100000$，所有输入的数均在$\text{int}$范围内，不强制在线。
- $1\leq l\leq r\leq n\leq 50000$，所有输入的数均在$\text{int}$范围内，强制在线。
$\text{TL:1000ms}$
思路
好像和原题没什么关系了……
不强制在线的话，可以先离散化，然后分成$\sqrt{n}$大小的块。
每个块用$O(n)$的空间存储每种数的数量，如果全部相同则打$\text{tag}$。
首先，单点修改是$O(1)$的（某种数的数量$+1$，某种数的数量$-1$），整块修改也是$O(1)$的（打$\text{tag}$）。
不完整的块的修改则是$O(\sqrt{n})$的（可能需要拆$\text{tag}$，拆掉后相当于整个块进行修改，也是$O(\sqrt{n})$的）。
查询时，显然对于整块是$O(1)$的，对于不完整的块暴力是$O(\sqrt{n})$的。
所以时间复杂度和空间复杂度都是$O(n\sqrt{n})$，可以通过此题。
强制在线的话，可以用$\text{map}$来使空间复杂度保持$O(n\sqrt{n})$，而时间复杂度将变为$O(n\sqrt{n}\log_2n)$，大概应该或许能通过此题。
因加强版未找到题目，对于强制在线的时间复杂度，若能在保证空间的情况下做到更优，欢迎在评论区指出或私信本人！
代码
1 |
|
数列分块入门 9
题意
给出一个长为$n$的数列，以及$n$个询问，询问涉及求区间最小众数。
$1\leq l\leq r\leq n\leq 100000$,输入的所有数均为$\text{int}$范围的整数，不强制在线。
思路
离线下来，做个莫队，块大小$\lfloor\frac{n}{\sqrt{n\log_2n}}\rfloor$。
具体实现我不会……啊啊我好菜
代码
我不会啊
加强
强制在线。见强制在线不带修区间众数。