首先，為什么要有離散化呢？

比如這道題，我們應該開一個差分數組，但是a，b之間的間隔可是太大了，難道我們要開一個2的三十二次方大小的數組嗎？我們也是開不了這么大的數組的

我們就需要把這些數離散化，映射到一個小于n的數組里面

比如[99,9,9999,999999,99,9]

如果我們要直接映射到一個哈希表上就要開一個10的6次方大小的數組，但是我們不用這么做

這種數據量小但是數據范圍大的情況，我們可以把它從小到大依次映射

9就是編號1，99就是編號2，9999就是編號3，999999就是編號4

這種就是叫做我們的離散化

實現我們的離散化有兩種方法，一種就是排序+去重+二分

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], disc[N];
int n;
int pos;
int find(int x)
{int l = 1, r = pos;while (l < r){int mid = (l + r) / 2;if (disc[mid] >= x) r = mid;else l = mid + 1;}return l;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];disc[++pos] = a[i];}sort(disc + 1, disc + 1 + pos);pos = (unique(disc + 1, disc + 1 + pos) - (disc + 1));for (int i = 1; i <= n; i++){cout << a[i] << "離散化后是：" << find(a[i]) << endl;}return 0;
}

另一種方法就是利用哈希表unordered_map? map是雙元的，第一個int存原始值，第二個int存離散化之后的值，我們就直接從小到大遍歷dict數組，把每個原始值都編上號，重復的不編，然后我們再遍歷原數組，通過原始值找對應的編號（這里直接下標訪問就行了）

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int a[N],disc[N];
int main()
{int pos = 0;cin >> n;for(int i =1;i<=n;i++){cin >> a[i];disc[++pos] = a[i];}sort(disc+1,disc+1+pos);unordered_map <int,int> mp;int cnt = 0;for(int i = 1;i<=pos;i++){int x = disc[i];if(mp.count(x)) continue;++cnt;mp[x] = cnt;}for(int i= 1;i<=n;i++){cout << a[i] << "離散化之后的值:" << mp[a[i]] << endl;}
}

我們回到火燒赤壁這道題來，apprently這道題是要用差分做的，但是如果我們直接差分的話，這個區間可以達到最大是2^32 我們是開不了這么大的數組的，所以我們就要用到所謂離散化

我們把每個數都離散化，然后遍歷每個區間，用差分數組對離散化后的區間進行整體+1

然后還原差分數組，統計每個區間（這時候區間個數要用原數據來算）

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 2e4+10;
int a[N],b[N];
int f[N*2],disc[N*2];
unordered_map<int,int> mp;
int n;
int pos;
int main()
{cin >> n;for(int i = 1;i<=n;i++){cin >> a[i] >> b[i];disc[++pos] = a[i];disc[++pos] = b[i];}sort(disc+1,disc+1+pos);pos = unique(disc+1,disc+1+pos)-(disc+1);for(int i =1;i<=pos;i++){mp[disc[i]] = i;}for(int i = 1;i<=n;i++){int l = a[i],r = b[i];f[mp[l]]+=1;f[mp[r]]-=1;}for(int i = 1;i<=pos;i++){f[i]+=f[i-1]; }int ret = 0;for(int i = 1;i<=pos;i++){int j = i;while(f[j]!=0 && j<=pos){j++;}ret+=disc[j]-disc[i];i = j+1;}cout << ret << endl;return 0;
}