块状思想自学
目录一些定义：
分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。
分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。
分块是一种很灵活的思想，相较于树状数组和线段树，分块的优点是通用性更好，可以维护很多树状数组和线段树无法维护的信息。
当然，分块的缺点是渐进意义的复杂度，相较于线段树和树状数组不够好。
（转载自oiwiki）
引入
为什么要有分块思想？
首先可以明确一下，对于线段树这样的数据结构，我对一些题目而言，相对于分块思想肯定是更加优秀的。
但是数据结构和分块思想的区别度还是很大的，可以说，线段树能做的分块也能做，但时间不优秀。但是，分块能做的线段树可能非常难维护。
就比如说，要求你写一个程序，给你一串数字，有以下两种操作：
- 修改l-r之间的数字全部变为x。
- 给两个数字x,y。求在这个数列里面最近的两个x,y的距离，没有则输出-1。
数据范围在1e5的样子（序列长度和询问次数）
如果这种题叫你去写线段树平衡树这样的结构的话，显得无厘头，我这维护什么啊？总不可能每一段里面的每两个数都维护个最近距离吧。
先思考为什么不能用线段树做：线段树对“结合律”很有要求。
这时候应该就是分块来暴力了。
A. 分块思想：
例题引入：
思路引导
这道题大概就是两种操作，一种是区间加，一种是区间求和。
很显然线段树什么的可以乱杀，但是这里要选择分块思想来训练。
我们先假设我们把整个序列分为了很多个块，每个长度为 根号n。
预处理部分：求出每一个块的和。
修改部分：对于开头的不完整块和结尾的不完整块暴力求解，中间的块整体加，这时候注意下，对于不完整块的修改，需要在原数组上直接修改，其余的只修改lz_tag。
为什么这样做呢，实际上就相当于把不整的块的lazy_tag直接下传了，但是整块的就不下传啦。
求解部分：开头与结尾暴力求解，中间的直接用处理的数组直接加就好，当然这样子做的话需要laz_tag，写着写着就会发现需要记录。
复杂度分析：暴力部分由于分了块，我最多会暴力 根号n 次，而对于中间的，由于最多 根号n 个块，每个块我预处理了的，所以也是根号n的时间。
所以总共大概是 2n根号n的时间复杂度。
ac代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int num[500005];
int sum[750];//每一块大概是750的长度
int lz[750];//记录每一块的lz_tag。
int sq;
int ingrp(int x){//寻找在哪一个分块中
return ceil(1.0*x/sq);
}
int findid(int x){//寻找在分块中的排位
if(x%sq!=0)
return x%sq;
else
return sq;
}
signed main(){
ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> num[i];
}
sq=floor(1.0*sqrt(n));//块长
for(int i=1;i<=n;i++){
int gp=ingrp(i);
sum[gp]+=num[i];//求每一块和（预处理）
}
for(int i=1;i<=n;i++){
int opt,l,r,c;
cin >> opt >> l >> r >> c;
if(opt==0){
int sgp=ingrp(l);
int tgp=ingrp(r);
int pos=l;
if(sgp!=tgp){//相等的时候同一段会被计算两次，这一部分加上这个那么对同一段而言就不会计算两次了
sum[sgp]+=c;
num[pos]+=c;//直接下传lz，所以不修改lz
while(ingrp(pos+1)==sgp&&pos+1<=n&&pos+1<=r){
pos++;
sum[sgp]+=c;
num[pos]+=c;
}
}
pos=r;
sum[tgp]+=c;
num[pos]+=c;
while(ingrp(pos-1)==tgp&&pos-1>=1&&pos-1>=l){
pos--;
sum[tgp]+=c;
num[pos]+=c;
}
for(int j=sgp+1;j<=tgp-1;j++){//中间部分修改
sum[j]+=(c*sq);
lz[j]+=c;
}
}
else{
int ret=0;
int mod=c+1;
int sgp=ingrp(l);
int tgp=ingrp(r);
int pos=l;
if(sgp!=tgp){
int re=(num[l]+lz[sgp])%mod;
while(ingrp(pos+1)==sgp&&pos+1<=n&&pos+1<=r){
pos++;
re+=(num[pos]+lz[sgp])%mod;
}
ret+=re;
ret%=mod;
}
pos=r;
int re=(num[r]+lz[tgp])%mod;
while(ingrp(pos-1)==tgp&&pos-1>=1&&pos-1>=l){
pos--;
re+=(num[pos]+lz[tgp])%mod;
}
ret+=re;
ret%=mod;
for(int j=sgp+1;j<=tgp-1;j++){//中间部分修改
ret+=sum[j]%mod;
ret%=mod;
}
cout<<ret<<endl;
}
}
}
一些总结：
- 对于这个模板而言，不论是思想还是代码都好做。但可能存在变一下柿子然后很难的情况，所以要加强训练这种题目。
建议还是自己写一下。 - 如果可以的话，还可以进行对询问的分块，但这种题应该很少（其实是我没理解放了水罢了）
如练习的第一题，就是对询问进行了根号分治。
一些小练习：（题解晚点写出来）
https://codeforces.com/contest/786/problem/C
又：https://www.luogu.com.cn/problem/CF786C
题解：https://www.cnblogs.com/linghusama/p/17675699.html
https://codeforces.com/contest/840/problem/D
https://codeforces.com/contest/13/problem/E
https://codeforces.com/problemset/problem/617/E
https://codeforces.com/problemset/problem/86/D