《C++入门到入土》——分 块
分块，是一个在C++中的一个算法（废话）。这个算法和它的名字一样，是通过将数据分成许多的块，然后将每个块进行预处理，将我们需要的值先通过O(n)计算出来，然后读取某一块时就可以以O(1)的速度读取，节省了一定的时间复杂度。
通过这个方法可以计算一些关于区间的问题。例如“最优贸易简化版”。这个在洛谷是找不到原题的，题目如下：
题目描述
C国有 n 座城市，编号是 1 到 n ，编号为 i 的城市有路到编号为 i+1 的城市（编号为 n 的城市没有路到其他的城市）。
C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙再次来到C国旅游。他还是想贩卖水晶赚取旅费，在某个城市买入，再另一个城市卖出。
他将从编号为 a 的城市到编号到 b 的城市。请你帮他算算，最多能赚多少钱。
注：他最多进行一次买入和一次卖出。
输入格式
第一行两个整数n和m，表示n个城市和m个询问。 第二行n个整数，表示n座城市水晶的买入和卖出的价格。 接下来m行，每行两个整数a,b，表示阿龙要从编号为a的城市到编号为b的城市（保证a<b）。
输出格式
对于每个询问输出阿龙最多能赚多少钱。
输入输出样例
输入 输出
6 3 0 5 5
2 1 3 6 4 5
1 2
2 4
1 6
说明/提示
从1到2，无法赚钱。 从2到4，在编号为2的城市买入，在编号为4的城市卖出。 从1到6，在编号为2的城市买入，在编号为4的城市卖出
n,m <= 1e5;价格不小于 1e9；
看题目：首先，这道题中是有多次访问的。如果按照普通的方法，m次访问，每次从a到b扫一遍，时间复杂度应该是O(mn)，这样是肯定超时的。而如果按照上面的分块思想，将一个区间内所需的值（最大值mai，最小值ma，区间内的最优值v）算出来，在访问这个区间是只需要将算出的值进行计算就行了。
思考一个问题：怎样分区间，使得区间内的数尽可能多且能够得出尽可能多的区间？
如果区间内的数多，那么所需计算的区间就少了；区间多了，就可以在左右范围内包含更多的区间：所以，最好的方式就是建立√n个区间，内含√n个数，多出的数再成一个区间。由此，我们可以得出区间的初始化状态：
随后，每次输入一个起点城市a和终止城市b。因为有多个访问，且计算步骤相同，所以可以设定一个函数来计算。
首先需要看a和b位于哪一个区间。因为每个区间是s个数，所以a所在区间就是a/s，b所在区间就是b/s。同时设定一个ans记录答案；minn记录可a到b之间购买所需最少的钱，初始值就是最开始的城市价格。l是最左端，表示a城的编号；r和l相反，表示b城编号。
随后，我们需要考虑多种情况：
一：a和b在同一区间内，此时s1=s2。注意，我们计算时，是将整个区间处理的，
如果不是包含整个区间，我们就需要将此区间遍历一遍。
因此，我们在s1=s2时，需要依次从a到b遍历一遍，求出购买所花最少的钱和售出最大的钱。
二：否则的话，就是跨区间访问了，这时我们分块的作用就要体现出来了。
但这时，我们要花三种情况讨论：
1：从a城市开始，到a城市所在区间的最后一个城市。这段肯定是不能包括一整个区间的，所以需要将其遍历一遍：
这里解释一下i<s*(s1+1)：s1是a城市所在区间，s1+1就是a城市下一个区间的编号，每个区间有s个数，所以s*(s1+1)就是a城下个区间里的第一个城市编号。而i<s*(s1+1)就是到a城下个区间里的第一个城市的上一个城市，也就是a区间的最后一个城市，等同于i<=s*(s1+1)-1。
2：在a城市到b城市中间的区间。每个区间有三个值：区间内的最大值、最小值和最优值。这时的ans就不能只看两个数了，需要考虑三个数：
ans的当前值；
这个区间内的最大值；
还有一个有时会忽略的值——区间的最大值减去当前最小值。
至于为什么是三个值的最大值，可以自己思考一下很简单的
这里s1+1是a城市的下一个区间，i<s2是要在b城市的上一个区间停下。
因为区间内的最小值已经算出来了，所以在更新最小值时只需要将其与该区间的ma值对比。
3：从b城市所在区间的第一个城市到b城。这一段和第一种讨论是几乎一样的，依次遍历。
到这里，主程序和函数部分就讲完了，接下来就直接放完整代码了：
以上就是分块思想及其基本例题，有能力（比我强的）可以去尝试：
洛谷P2357 守墓人（https://www.luogu.com.cn/problem/P2357）
洛谷P3870 [TJOI2009] 开关（https://www.luogu.com.cn/problem/P3870）
完结撒花（祈愿胡桃单抽出护摩）
