分块

这是一个没咕多久但还是咕咕咕了的分块学习笔记……

先从一个问题引入吧：

给一个序列，支持求区间和

我：前缀和吧

还要支持区间修改（区间加一个数）

我：线段树可以

还要支持求区间小于k的数的个数，且每次询问的k都不一定相同

我：太难了/dk

另：卡平衡树

……

分块就可以解决这个问题/cy。分块，可以说是一个优雅的暴力。顾名思义，分块，就是把一个序列分成几个块来维护。

我们把一个长度为\(n\)的序列分成\(\sqrt{n}\)块，每块有\(\sqrt{n}\)个元素，多余的部分再分一块。对于每一块可以维护整体的信息。
接下来来看上面的几种操作怎么维护。

求区间和

对于一个区间，我们可以把他分成：左碎块，中间的整块，右碎块。
对于中间的整块，我们可以直接求。而左碎块和右碎块，也就是左右不满一块的部分，我们可以暴力求。因为一块最大\(\sqrt{n}\)个元素，所以枚举一遍还是很快的。

区间修改

这里，首先我们绝对不可能一个个枚举修改的。那怎么办呢？我们可以像线段树一样，维护一个标记。\(f_i\)表示第\(i\)个块里的每个元素都要加上\(f_i\)，那整块就要加上\(\sqrt{n} \times f_i\)。这是对于整块的。
那么对于左碎块和右碎块呢？自然也是直接枚举啊。枚举谁不会， 在枚举过程中，别忘了维护区间整块的大小哦！

求区间内\(\le k\)的数的个数

这里，我们可以同时维护另一个序列，这个序列中，每个块都是有序的，可以发现有序的块也可以同时实现上面的操作，然后在查询时，只要对每个块二分即可。

对于上面给出的那个题，有一个类似的就是 [Ynoi2017]由乃打扑克，以及 题解

接下来看一道模板题：P2357 守墓人

这里，减\(k\)其实可以看做加\(-k\)，而这个求主墓的风水其实是迷人眼球的，根本没有什么特殊的用处，当普通的求就好了。

code：

#include
#include
#define ll long long
using namespace std;
int n,m;
ll a[200005];//初始序列
int sq,q[200005];//sq=sqrt(n)，qi表示i所在的块的编号
ll res[200005],f[200005];//resi表示第i个块的大小（指区间和），fi表示第i个块的标记
int min(int x,int y){return x