1
操作涉及区间加法,单点查值。
对于每个块维护一个 \(ad\) 数组表示这个块每次修改增加的值的和,在修改 \(l\) ~ \(r\) 区间时,如果 \(l,r\) 在同一个块,那直接暴力修改。否则对于 \(l\) ~ \(R_{bel_l}\) 和 \(L_{bel_r}\) ~ \(r\) 这两个散块暴力修改,中间的整块将 \(ad_i\) 累加 \(c\) 就行了。
因为块长为 \(\sqrt {n}\),所以每次操作都是 \(\mathcal {O(\sqrt {n})}\) 的。
总时间复杂度 \(\mathcal {O(n \sqrt {n})}\)。
2
操作涉及区间加法,询问区间内小于某个值 \(x\) 的元素个数。
小于 \(x\) 的元素个数直接求是不好做的,复杂度上天。但是如果区间有序,那我们就可以二分 \(x\) ,从而快速求出答案。具体的,我们考虑直接把整块排序,在区间加时,因为整块都被加上了一个整数,所以顺序并不影响。对于散块,直接把里面的数提出来重排一遍(注意重排要将整个区间都排一遍,不能只排散块)。
查询的话整块直接 lower_bound 一下,散块暴力找就行了。
复杂度:\(\mathcal {O(n \sqrt {n} \log{\sqrt {n}})}\)
3
操作涉及区间加法,询问区间内小于某个值 \(x\) 的前驱(比其小的最大元素)。
与T2几乎一样?注意在 lower_bound 时减 \(1\) 才是严格小于 \(x\) 的数。就完了。
复杂度:\(\mathcal {O(n \sqrt {n} \log{\sqrt {n}})}\)
4
操作涉及区间加法,区间求和。
板子题。维护一个懒标记就好了。
复杂度:\(\mathcal {O(n \sqrt {n})}\)
5
操作涉及区间开方,区间求和。
注意一个性质:一个数开一次方是 \(\sqrt x\),再开一次就变成了 \(\sqrt[2^2]{x}\),再开 \(\sqrt[2^3]{x}\) \(\cdots\)这个指数增长很快,开个 \(5,6\) 次就到 \(1\) 了。于是我们可以维护一个 \(flag\) 表示整块中是否有数 \(>1\),每次更新散块暴力修改,整块看 \(falg\) 是否为 \(1\),是就跳过,否则进入这个块暴力修改,同时更新 \(flag\)。于是我们就做完了。
复杂度:\(\mathcal {O(n \sqrt {n})}\)
6
操作涉及单点插入,单点询问。
可以考虑对于每个块维护一个 vector
,单点插入就去枚举每个块,看当前位置在哪个块中,直接用这个块的 vector
insert 就行了。块长 \(\sqrt n\),因此单次操作 \(O(\sqrt n)\)。查询同理,看他在哪个块直接访问 vector
就行了。但这样有个问题:可能一直往某一个块内加东西,就会让这个块长度爆炸。于是可以在块长 \(\ge 2 \sqrt n\) 把整个序列重新分块,每次 \(O(n)\),最多 \(\sqrt n\) 次,因此总复杂度 \(O(n \sqrt n)\)。
7
操作涉及区间乘法,区间加法,单点询问。
维护一个形如 \(k\times a_i + b\) 的懒标记。每次加法就对整块的 \(b\) \(+c\),乘法就把 \(k,b\) 都 \(\times c\)。但是散块就不能这样处理,因为不能去修改整块的懒标记,但是不改懒标记又改不了 \(a_i\),因此可以考虑把散块直接重构,先把每个 \(a_i \gets k \times a_i+b\),同时 \(k=1,b=0\),再进行懒标记的更新就好了。\(O(n\sqrt n)\)。
8
操作涉及区间询问等于一个数 \(c\) 的元素,并将这个区间的所有元素改为 \(c\)。
区间赋值不难想到维护一个区间 \(flag\),表示这个块是否被整体变成了一个数。如果是,那么就可以 \(O(1)\) 查询和修改了。若不是,那么就进入块暴力查找和修改,\(O(\sqrt n)\)。这样看上去很玄学,但是,虽然我们是 \(O(\sqrt n)\) 暴力查,但是查了之后就会立即给它赋上 \(flag\) 的,在之后的操作中,如果这个块被视作整块来操作,那么它就可以直接 \(O(1)\) 判断 \(flag\) ,再往后也是这样。如果不是整块操作,那就是暴力查,但是每次查询最多有两个非整块,所以这个暴力操作被执行的次数是 \(O(n)\) 的,这东西整体复杂度就是 \(O(\sqrt n)\)。(摘自 MrcFrst_LRY)
9 P4168
操作涉及询问区间的最小众数。
既然要求众数,那么每个数字出现的次数就必须要被记录下来。于是我们记 \(sum_{i,j}\) 表示在前 \(i\) 个块中,数字 \(j\) 的出现次数。以及 \(p_{i,j}\) 表示块 \(i-j\) 的众数。对于 \(sum\),直接 \(\mathcal {O(n \sqrt {n})}\) 预处理;对于 \(p\) ,枚举两个块号 \(i,j\),\(j\) 从 \(i\) 开始,每次当前众数从 \(p_{i,j-1}\) 开始,暴力扫 \(j\) 这个块,看能否更新 \(p_{i,j}\)。\(\mathcal {O(\sqrt n \times \sqrt n \times \sqrt n)} = \mathcal{O(n \sqrt {n})}\)。这样便预处理完了两个数组。每次查询时,先以区间中所有整块的众数为答案,在用一个桶去记录散块中每个数的出现次数,并看他们有没有可能在询问区间中的出现次数大于当前众数的出现次数,可以的话就更新答案。便做完了。
复杂度:\(\mathcal {O(n \sqrt {n})}\)