根号算法（分块、莫队、根号分治）
根号算法一直以来被称为所谓“优美的暴力”。其大致思路是设定一个块长 \(len\) 。如果数据规模（包含操作与询问）小于等于这个块长就去暴力。如果大于块长，那假设可以快速处理或者给数据规模为 \(len\) 的操作或者询问打标记，那么就只需要处理 \(\frac{n}{len}\) 个这种区间。可以发现，当 \(len=\sqrt{n}\) 或者 \(len=\frac{n}{\sqrt m}\) 时（\(n\) 为区间长度，\(m\) 为操作与询问次数），时间复杂度接近平衡。
因此，这种设定一个块长（一般为 \(\sqrt n\)）根据询问与操作的数据规模和块长的大小关系来维护区间，因此时间复杂度带 \(\sqrt n\) 的算法，我们将之称为根号算法。
根号算法一般包括分块、莫队、根号分治 以及乱搞。虽然根号算法有很多类算法，但是一般将其一起看，因为三者之间互有共通之处。
同时这三种算法变化又很多，思路很灵活，一般都是思维题 与码量题，因此直接放在一起了。
分块
前言
分块是有很多套路的，当然也有很多变化。首先最基础的就是对什么东西分块，例如：
[*]直接对序列本身分块。
[*]对值域分块
[*]对时间轴分块
等等。上述三种是比较常见的。但是这只是最基础的，扩展有倍增值域分块、套用其他数据结构比如树状数组线段树一类的。这些就需要特别去练习了。
特别需要注意的是分块与扫描线的结合。将分块挂在扫描线上是一种有很强的可扩展性的数据结构。其应用（特别是在Ynoi中）相当多。
同时其本质清楚、画图的话结构比较明了，但有时难度相当大，需要勤加练习掌握套路。
对序列分块
[*]这是最基础的根号算法了。将序列上每连续的 \(len\) 个数（即块长个数）分为一个“块”，然后去通过这个块来维护与统计序列。
P2801 教主的魔法
修改：区间加 ，查询：区间排名
非常典的一道题。考虑一个套路：将序列按 \(\sqrt n\) 分块。维护两个序列，一个是原序列。一个是在每个块内按权值排完序后的序列。
这样做对于查询的好处是显而易见的：对于整块直接在排完序的块中二分查找到排名，对于散块直接在原序列上暴力一个一个枚举看是否大于所询问的值。最后将比查询的值小的数的个数加起来即可。
同时可以发现，区间加整块并不会改变原来排过序之后值的相对位置。因此只需要打区间加标记就可以了。修改对于散块而言就直接暴力重构即可。
code
需要注意的一个点是由于我们打了区间加标记，对于每一块分别查询的时候，假设当前块的区间加标记是 \(tag\)，查询的值是 \(C\)，那实际二分查找的值应该是 \(C-tag\)，这样就不需要下放标记了。
同时根号算法的题一般都是可以设定一个固定的块长的，可以比较明显的看出只要块长设定范围合适，算法在数据范围内复杂度仍然正确。同时固定的块长会方便卡常一点
说的好像有点抽象，具体可以看看代码。复杂度 \(\sqrt n\times \sqrt n\log \sqrt n-q\sqrt n\log \sqrt n\)。这里 "-" 前后分别代表预处理的复杂度以及执行查询与询问操作的复杂度。后面的例题基本也会这样来表示复杂度。
点击查看代码#includeusing namespace std;const int N=1e6+7;const int len=1005;int n,m,a,bel,l,r,b,num=0,tag;void modify(int ql,int qr,int w){ int loc=bel; for(int i=ql;in>>m; for(int i=1;i>a,b=a,bel=(i-1)/len+1;if((i-1)%len==0)l]=i,num++;if(i%len==0||i==n)r]=i;} for(int i=1;iop>>ql>>qr>>w; if(op=='M') { if(bel==bel) {modify(ql,qr,w);continue;} modify(ql,r],w),modify(l],qr,w); for(int j=bel+1;jmx-x\)，即贡献也是 \(x\)。
也就是枚举次数与贡献是线性的，或者说同步的。因此对于每一块的总修改的复杂度是 \(O(值域)\) 的。
再以那个暴力为例。
每次是枚举 \(\)，而 \(mx->mx-x\)，即贡献是 \(x\)。这时枚举的次数与其贡献是不对等的。当 \(x\) 够小时这个暴力就爆了。</p></blockquote>综上，对于每一个块，我们修改的总复杂度是 \(O(值域)\) 也就是 \(O(n)\) 的。所有块合起来就是 \(O(n\sqrt n)\) 的。
然后发现在代码实现上，由于修改的时候不需要在并查集上去 \(find\)，因此遍历时是 \(O(1)\) 修改的。这样修改的总复杂度就是对的。
查询的话就是如果是查询整块就可以直接在并查集上找到其对应的值的 \(size\)。如果是散块就暴力枚举。但是散块这里还要乘上一个并查集路径压缩的时间。但是听机房大佬说这是反阿克曼函数可以当成 \(O(1)\) 的。因此这里并查集的复杂度就被处理掉了。
具体而言，我们平常说的“并查集是 $\log $ 的”的说法是对的，因为修改操作几次后查询这样交替的操作方式的复杂度就是近似 \(O(\log n)\)。
但是这里的复杂度是一个类似于均摊一样的东西去保证的。我们是修改一个块的若干个节点后查询整个块的所有节点的初始值，而这样的话对于一整个块而言路径压缩的次数最多就 \(n\) 次。因此并查集的复杂度在这里是 \(O(1)\) 的。（好像比较感性？）
总时间复杂度 \(O(n\sqrt n)\)。
然后就发现过不了一点。因为空间也是 \(O(n\sqrt n)\) 的，但是lxl只开了64MB。
因为每一块之间的修改与查询都没有关系。因此可以考虑可以用逐块处理。然后空间复杂度就是 \(O(n)\) 了
code
细节有，卡常也有。记得好好调一调块长。
点击查看代码#includeusing namespace std;#define gc getcharint rd() { int x = 0, f = 1; char c = gc(); while(c < '0' || c > '9') { if(c == '-') f = (- 1); c = gc(); } while(c >= '0' && c
页:
[1]