離散化，把無(wú)限空間中有限的個(gè)體映射到有限的空間中去，以此提高算法的時(shí)空效率。通俗的說(shuō)，離散化是在不改變數(shù)據(jù)相對(duì)大小的條件下，對(duì)數(shù)據(jù)進(jìn)行相應(yīng)的縮小。

離散化的本質(zhì)，是映射，將間隔很大的點(diǎn)，映射到相鄰的數(shù)組元素中。減少對(duì)空間的需求，也減少計(jì)算量。而映射最大的難點(diǎn)是前后的映射關(guān)系，如何能夠?qū)⒉贿B續(xù)的點(diǎn)映射到連續(xù)的數(shù)組的下標(biāo)。

舉例來(lái)說(shuō)，有一些數(shù)值，在一個(gè)很大的范圍里，比如0~10^10的區(qū)間，但個(gè)數(shù)極少。這樣一來(lái)， 直接開(kāi)這么大的數(shù)組，根本不現(xiàn)實(shí)。因?yàn)榇鎯?chǔ)的下標(biāo)實(shí)在太大了，所以需要進(jìn)行映射，而映射的過(guò)程就是離散化。

再比如，有一個(gè)數(shù)組a，分別存儲(chǔ)了1，400，8000，6000000。依次將其映射到1，2，3，4，這個(gè)過(guò)程就是離散化。

離散化的過(guò)程中一般會(huì)遇到這兩個(gè)問(wèn)題，a數(shù)組具有重復(fù)元素以及如何換算a[i]離散化的值的問(wèn)題。

解決的方法一般為去重和二分。

區(qū)間和?

假定有一個(gè)無(wú)限長(zhǎng)的數(shù)軸，數(shù)軸上每個(gè)坐標(biāo)上的數(shù)都是?0。

現(xiàn)在，我們首先進(jìn)行?n?次操作，每次操作將某一位置?x?上的數(shù)加?c。

接下來(lái)，進(jìn)行?m?次詢問(wèn)，每個(gè)詢問(wèn)包含兩個(gè)整數(shù)?l?和?r，你需要求出在區(qū)間?[l,r]?之間的所有數(shù)的和。

輸入格式

第一行包含兩個(gè)整數(shù)?n?和?m。

接下來(lái)?n?行，每行包含兩個(gè)整數(shù)?x?和?c。

再接下來(lái)?m?行，每行包含兩個(gè)整數(shù)?l?和?r。

輸出格式

共?m?行，每行輸出一個(gè)詢問(wèn)中所求的區(qū)間內(nèi)數(shù)字和。

區(qū)間和思路

開(kāi)辟額外的動(dòng)態(tài)數(shù)組add存放要被加上c的位置下標(biāo)，同時(shí)存放要加上去的c（移動(dòng)下標(biāo)，改變坐標(biāo)軸上的c）。

開(kāi)辟額外的動(dòng)態(tài)數(shù)組query存放查詢的數(shù)組下標(biāo)的l，r。

因此，需要一個(gè)pair<int, int>類型作為動(dòng)態(tài)數(shù)組的類型。

（pair是將2個(gè)數(shù)據(jù)組合成一組數(shù)據(jù)，類似于map<key, value>。pair將一對(duì)值組合成一個(gè)值，這一對(duì)值可以具有不同的數(shù)據(jù)類型（T1和T2），兩個(gè)值可以分別用pair的兩個(gè)公有函數(shù)first和second訪問(wèn)。）

開(kāi)辟額外的動(dòng)態(tài)數(shù)組alls存放所有數(shù)組下標(biāo)，或者說(shuō)下標(biāo)標(biāo)志，包括詢問(wèn)里的區(qū)間的坐標(biāo)

開(kāi)辟額外的數(shù)組a存取離散化后的數(shù)組下標(biāo)對(duì)應(yīng)的值。

然后開(kāi)辟額外數(shù)組s存取前綴和數(shù)組，用于求[l,r]?之間的所有數(shù)的和。

簡(jiǎn)單來(lái)說(shuō)，就是用動(dòng)態(tài)數(shù)組來(lái)存儲(chǔ)下標(biāo)和需要加上的值，用數(shù)組存儲(chǔ)真正的數(shù)組值。

也就是說(shuō)，先在動(dòng)態(tài)數(shù)組來(lái)存儲(chǔ)下標(biāo)和需要加上的值，再在遍歷中實(shí)現(xiàn)存儲(chǔ)真正的數(shù)組值。

在依次處理好動(dòng)態(tài)數(shù)組的存儲(chǔ)后，進(jìn)行排序和去重以便更好的實(shí)現(xiàn)二分（二分查找需要考慮序列中存在具體解以及序列必須有序）。

在遍歷中，先將alls的值依次插入值數(shù)組a，即先用二分查找（提高效率）處理x，再加上c（前者為.first，后者為.second）。再進(jìn)行前綴和求取。

最后，利用前綴和求取區(qū)間和（區(qū)間和就是前綴和來(lái)求的某一段和。采用前綴和思想來(lái)提高效率）。

過(guò)程中，對(duì)alls的改動(dòng)就是離散化的過(guò)程（存儲(chǔ)下標(biāo)）。

區(qū)間和過(guò)程

1.讀入和輸入。將每次讀入的位置x和加數(shù)c存到到add中，將每次讀入的位置x存到到alls中，將每次讀入的左下標(biāo)l和右下標(biāo)r存到到query中。

2.進(jìn)行排序、去重。

3.遍歷，完成在離散化的數(shù)組映射到的a數(shù)組中進(jìn)行加上c的操作（利用find函數(shù)）。

4.預(yù)處理前綴和s數(shù)組。

5.通過(guò)遍歷query，完成求區(qū)間[l,r]的和。

alls.push_back(l);?alls.push_back(r); 的用處在于l與r這兩個(gè)下標(biāo)上由于未必存取了相關(guān)值，因此在將add中存儲(chǔ)到alls里的時(shí)候，該位置很可能為空。而二分查找需要一個(gè)確定的范圍，所以先加上，而該下標(biāo)已經(jīng)存儲(chǔ)的話，則由最后進(jìn)行排序去重部分進(jìn)行消除。

排序與去重中，unique(alls.begin(), alls.end())負(fù)責(zé)去重，alls.erase(unique(alls.begin(), alls.end()), alls.end())負(fù)責(zé)去除去重后遺留的不存在值得數(shù)組。

疑惑，其實(shí)并沒(méi)有完全學(xué)懂，就是盡己所能的記下來(lái)先。