$$优雅的暴力 --- 分块$$
【说明】：
其顾名思义， 也就是一段数列分成一块一块的，从而更快的维护什么东西。
【实现】：
在说明它的实现之前，我们提出一系列的问题；
1.求出一段区间的区间和（这个我会，前缀和搞一下）
2.在一段区间上加上一个值（这个我会，线段树来一手，乘法也可以）
3.查询一段区间上有多少个数(<k) ((k>0)且给定) (这个我熟，平衡树)
(OK),括号里面的统统屏蔽掉，我不会了。可能你想的太深了，一直追求一个优秀的时间复杂度，我们先抛弃这个想法，来一遍朴素的
那么朴素的怎么搞呢 ？
- 第一个问题， 那还是前缀和搞一下吧，就是最基本了
- 第二个问题， 对于每一个区间 ([l, r])，我们直接枚举从(l)到(r),然后加上
3.第三个问题，我们还是从(l)到(r) ,枚举区间 那么 (ans = sum limits _{i = l} ^r a[i] < k),然后就是答案
是不是呆呆的，那么好，我们让其不呆呆的，如果学过线段树的话，那么这个也就十分好理解了。
我们引入分块，我们将其分解，将整个的数列分成(sqrt{n})块， 每一块中包含(sqrt{n})个元素，（我发现了，(sqrt{n} imes sqrt{n} = n) ,太厉害了）,分块就是这么一个思想。在这个每一个块里，我们都进行一个数据维护，类似于线段树一样，(可以用结构体存储，也可以用数组存，个人建议用结构体，一般不会卡，并且好理解，好写)
描述一下：
用到的一些语句：
现在解释几个本文用到的术语：
1.完整块：被操作区间完全覆盖的块
2.不完整块：操作区间不完全覆盖的块
然后我们先看看怎么得出答案：
问题1
1.对于完整的块，我们希望有个东西能直接找出这整个块的和，于是每个块要维护这个块的所有元素的和。
2.对于不完整块，因为元素比较少(最多有 总数n / 块数 = n−−√ 个) 这时候当n=1000000的时候最多有1000个，对比一下，我们可以直接暴力扫这个小块统计答案，
3.小技巧：如果这个不完整块被覆盖的长度>块维护的长度的一半，何不用这个块的和-没有被覆盖的元素的值呢？
问题2
这里，我们换种思路，记录一个lazy 标记(为什么用lazy，因为计算机很懒，他老是省时间),表示整个块被加上过多少了，
1.对于完整块，我们直接lazy+=加上的数x,块内的和ans+=x*元素个数(因为每个元素都被加上了x)
2.对于不完整块，直接暴力修改就好了，顺便可以把lazy标记清了。
问题3要在每个完整块内寻找小于一个值的元素数，
1.显然我们不得不要求块内元素是有序的，这样就能用二分(快速在一个有序的序列里查询的一个算法),对块内查询。
2.不完整的块暴力就好
3.这样的话需要提前对每块里面的元素做一遍排序就好.
4.但是当有修改的话，因为整个块同时加上(减去)一个数，每个数的相对大小是不会变的，但是如果是不完全块就会改变，这样的话，还是因为元素个数小，重新新排一下不就得了?
上 (hzwer , 黄学长)