线段树 1
区间加区间和。看看怎么暴力地分块。
考虑最暴力的做法就是 $O(n^2)$，但是可以将序列中一部分合成一个块来进行处理。
设块长为 $B$，那么就会分出 $\dfrac nB$ 个块，此时修改的时候最多会遍历 $\dfrac nB$ 个整块和 $2$ 个散块。我们在整块上打懒标记修改，在散块上暴力修改，因此此时时间复杂度是 $O\left(\dfrac nB+2B\right)$。
在查询的时候是同理的，我们另外维护每个块的和，整块拿和加上懒标记的影响、散块直接暴力加起来，此时时间复杂度是 $O\left(\dfrac nB+2B\right)$。
因此总时间复杂度是 $O\left(\dfrac nB+2B\right)$，取 $B=O(\sqrt n)$ 时复杂度最小，总复杂度是 $O(n\sqrt n)$。
教主的魔法
区间加、查询区间大于某数的值个数。
分块，考虑如何快速求整块的答案。我们新建一个辅助数组 $b_n$，并且对每个块将 $b$ 排序。此时在查询整块的时候就可以直接通过二分答案来求出答案。还是同样的，在对散块操作的时候直接暴力即可。
这样做复杂度是 $O(n\sqrt n\log n)$。
序列
两种操作：
- 区间加（可能为负数）
- 求 $a_p$ 在过去的时间里多少时间大于等于 $x$。
只有一个数怎么做？考虑对时间维分块，那么加一个数就相当于给这个时间加，查询就是查询 $[1,t]$ 内有多少数 $\ge x$，变成了教主的魔法。
考虑 $n$ 个数的情况，离线后用扫描线。扫描下标并且对时间维分块即可。复杂度是 $O((n+m)\sqrt m)$。
蒲公英
在线查询区间众数。
首先对 $a_i$ 离散化没的说。
如果支持离线就是莫队板子题，但现在要在线，因此考虑用啥数据结构来维护。线段树无法维护这个任务，因此考虑分块。
我们记 $s_{i,j}$ 为 $1\sim i$ 号块内 $j$ 的出现次数，$p_{i,j}$ 为 $i\sim j$ 号块内的众数。
考虑建块的时候预处理这两个数组，$s$ 可以 $O(n\sqrt n)$ 处理出来，$p$ 可以枚举 $i,j$ 后暴力枚举，复杂度仍然是 $O(n\sqrt n)$。
求答案的时候可以首先求出整块部分的答案，记它为 $P$。接下来我们枚举散块，并且设辅助数组 $cnt$ 为散块中每个数出现的次数，那么当前扫到的部分中 $i$ 出现的次数就是
然后直接在扫描过程中不断更新 $P$ 即可。注意在一次查询后要清空 $cnt$ 数组。
总时间复杂度显然是 $O(n\sqrt n+m\sqrt n)$，空间复杂度 $O(n\sqrt n)$。