loj 数列分块入门1-9

· · 个人记录

1. 区间加法，单点查值

左右区间暴力，中间整块打tag。查询直接输出a[r]+b[id[r]]。

code

2. 区间加法，询问区间内小于某个值x的元素个数

左右暴力，中间排序后用lower\_bound解决。

code

3. 区间加法，询问前驱

类似上一问，左右暴力，中间排序后lower\_bound解决。

code

4. 区间加法，区间求和

维护块内的和记为s[i]，区间加法时左右暴力加，中间打标记，并更新这些块内的和。询问时左右暴力枚举，加上中间的整块和。

code

5. 区间开方，区间求和

注意到一个数开到1之后开方就对它没有任何影响，于是我们可以对[l,r]上不为1的数暴力修改，并记录a[i]后下一个不为1的位置为nxt[i]。修改时可以顺便维护整块的和，查询和前几问没什么区别。

code

6. 单点插入，单点询问

首先看到单点插入和单点询问，不难想到我们学过的splay块状链表。只要把每个块大小维护在\sqrt{n}左右，找到pos位置就可以在O(\sqrt{n})的时间复杂度解决。找到该位置所在块后暴力插入也是O(\sqrt{n})的，查询是O(1)的。可以通过此题。

那么如何维护块的大小呢？我们只要在插入后判断该块大小，当块大小大于2\sqrt n时，就可以把该块分裂为两块。 然而这题数据太水导致我懒得这么写qwq

code

7. 区间乘法，区间加法，单点询问

看到这题就想到原来做过的线段树2。自然有了类似的做法：用乘法和加法两种懒标记，区间操作时左右两块直接暴力O(\sqrt n)下放，整块则是操作在标记上。询问时可以下放该块，也可以输出该点受标记影响的数值。

code

8. 区间询问并同时修改

对于询问中的整块，如果它没有打上标记，就暴力枚举块内的数并修改后打上标记；如果它有标记，则判断其标记是否为c。左右块也是类似的处理，对于有标记的左右块可以把标记下放，然后暴力枚举即可。由于这样最多只会让两块标记初始化，时间复杂度并不会爆炸，可以通过本题。

code

9. 静态区间众数

这里介绍一种在线做法。对于集合A\cup B的众数t，我们不难发现：

t\in \{A \text{的众数}\}\cup B

我们可以先对数据离散化，然后预处理出整块中每个数的个数。由于此题不带修改，我们可以通过前缀和优化来实现O(1)查询整块[L,R]之间c的个数。再通过前面的定理预处理出[L,R]区间的众数。

在处理询问时，可以用tmp[i]存储左右块内i的数量，然后枚举左右块中的所有a[i]，把它在[l,r]中的总数量（tmp[a[i]]+getsum(L+1,R-1,a[i])）与ans的数量进行比较，得出答案。考虑到memset可能导致超时，我们可以再次遍历左右区间并把tmp[a[i]]清空。

code

P.S.(双倍经验：P4168 [Violet]蒲公英)

巨佬要是用莫队秒题那就另当别论了