分塊，是一個在C++中的一個算法（廢話）。這個算法和它的名字一樣，是通過將數(shù)據(jù)分成許多的塊，然后將每個塊進(jìn)行預(yù)處理，將我們需要的值先通過O(n)計算出來，然后讀取某一塊時就可以以O(shè)(1)的速度讀取，節(jié)省了一定的時間復(fù)雜度。

通過這個方法可以計算一些關(guān)于區(qū)間的問題。例如“最優(yōu)貿(mào)易簡化版”。這個在洛谷是找不到原題的，題目如下：

題目描述

C國有 n 座城市，編號是 1 到 n ，編號為 i 的城市有路到編號為 i+1 的城市（編號為 n 的城市沒有路到其他的城市）。

C國幅員遼闊，各地的資源分布情況各不相同，這就導(dǎo)致了同一種商品在不同城市的價格不一定相同。但是，同一種商品在同一個城市的買入價和賣出價始終是相同的。

商人阿龍再次來到C國旅游。他還是想販賣水晶賺取旅費，在某個城市買入，再另一個城市賣出。

他將從編號為 a 的城市到編號到 b 的城市。請你幫他算算，最多能賺多少錢。

注：他最多進(jìn)行一次買入和一次賣出。

輸入格式

第一行兩個整數(shù)n和m，表示n個城市和m個詢問。 第二行n個整數(shù)，表示n座城市水晶的買入和賣出的價格。 接下來m行，每行兩個整數(shù)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掃一遍，時間復(fù)雜度應(yīng)該是O(mn)，這樣是肯定超時的。而如果按照上面的分塊思想，將一個區(qū)間內(nèi)所需的值（最大值mai，最小值ma，區(qū)間內(nèi)的最優(yōu)值v）算出來，在訪問這個區(qū)間是只需要將算出的值進(jìn)行計算就行了。

思考一個問題：怎樣分區(qū)間，使得區(qū)間內(nèi)的數(shù)盡可能多且能夠得出盡可能多的區(qū)間？

如果區(qū)間內(nèi)的數(shù)多，那么所需計算的區(qū)間就少了；區(qū)間多了，就可以在左右范圍內(nèi)包含更多的區(qū)間：所以，最好的方式就是建立√n個區(qū)間，內(nèi)含√n個數(shù)，多出的數(shù)再成一個區(qū)間。由此，我們可以得出區(qū)間的初始化狀態(tài)：

隨后，每次輸入一個起點城市a和終止城市b。因為有多個訪問，且計算步驟相同，所以可以設(shè)定一個函數(shù)來計算。

首先需要看a和b位于哪一個區(qū)間。因為每個區(qū)間是s個數(shù)，所以a所在區(qū)間就是a/s，b所在區(qū)間就是b/s。同時設(shè)定一個ans記錄答案；minn記錄可a到b之間購買所需最少的錢，初始值就是最開始的城市價格。l是最左端，表示a城的編號；r和l相反，表示b城編號。

隨后，我們需要考慮多種情況：

一：a和b在同一區(qū)間內(nèi)，此時s1=s2。注意，我們計算時，是將整個區(qū)間處理的，

如果不是包含整個區(qū)間，我們就需要將此區(qū)間遍歷一遍。

因此，我們在s1=s2時，需要依次從a到b遍歷一遍，求出購買所花最少的錢和售出最大的錢。

二：否則的話，就是跨區(qū)間訪問了，這時我們分塊的作用就要體現(xiàn)出來了。

但這時，我們要花三種情況討論：

????1：從a城市開始，到a城市所在區(qū)間的最后一個城市。這段肯定是不能包括一整個區(qū)間的，所以需要將其遍歷一遍：

這里解釋一下i<s*(s1+1)：s1是a城市所在區(qū)間，s1+1就是a城市下一個區(qū)間的編號，每個區(qū)間有s個數(shù)，所以s*(s1+1)就是a城下個區(qū)間里的第一個城市編號。而i<s*(s1+1)就是到a城下個區(qū)間里的第一個城市的上一個城市，也就是a區(qū)間的最后一個城市，等同于i<=s*(s1+1)-1。

????2：在a城市到b城市中間的區(qū)間。每個區(qū)間有三個值：區(qū)間內(nèi)的最大值、最小值和最優(yōu)值。這時的ans就不能只看兩個數(shù)了，需要考慮三個數(shù)：

ans的當(dāng)前值；

這個區(qū)間內(nèi)的最大值；

還有一個有時會忽略的值——區(qū)間的最大值減去當(dāng)前最小值。

至于為什么是三個值的最大值，可以自己思考一下很簡單的

這里s1+1是a城市的下一個區(qū)間，i<s2是要在b城市的上一個區(qū)間停下。

因為區(qū)間內(nèi)的最小值已經(jīng)算出來了，所以在更新最小值時只需要將其與該區(qū)間的ma值對比。

????3：從b城市所在區(qū)間的第一個城市到b城。這一段和第一種討論是幾乎一樣的，依次遍歷。

到這里，主程序和函數(shù)部分就講完了，接下來就直接放完整代碼了：

以上就是分塊思想及其基本例題，有能力（比我強的）可以去嘗試：

洛谷P2357 守墓人（https://www.luogu.com.cn/problem/P2357）

洛谷P3870 [TJOI2009] 開關(guān)（https://www.luogu.com.cn/problem/P3870）

完結(jié)撒花（祈愿胡桃單抽出護(hù)摩）