谈到分块,不得不说说 $\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$。
具体实现我不会……啊啊我好菜
代码
我不会啊
加强
强制在线。见强制在线不带修区间众数。