火烧赤壁
题目背景
曹操平定北方以后，公元 208 年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。
孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。
隆冬的十一月，天气突然回暖，刮起了东南风。
没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。
曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！
题目描述
给定每个起火部分的起点和终点，请你求出燃烧位置的长度之和。
输入格式
第一行一个整数，表示起火的信息条数 \(n\)。
接下来 \(n\) 行，每行两个整数 \(a, b\)，表示一个着火位置的起点和终点（注意：左闭右开）。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
3
-1 1
5 11
2 9
样例输出 #1
11
提示
数据规模与约定
对于全部的测试点，保证 \(1 \leq n \leq 2 \times 10^4\)，\(-2^{31} \leq a < b \lt 2^{31}\)，且答案小于 \(2^{31}\)。
解题思路
首先发现，数据量较少，数据区间很大，所以考虑使用离散化操作。
每次操作都是针对一个区间进行，所以我们可以考虑使用差分来进行区域操作。
这时会遇到一些问题。
由于题目中给出的区间为 左闭右开，因此如果存在两个区间相邻的情况（不叠加），所以右端点的操作应该是\(b[i]-=1\)而不是\(b[i+1]-=1\)。
我们假设有两个区间\([1,20)\)和\([45,400)\)这时可以发现，我们离散化之后得到的差分数组的前缀和为\(1，0，1，0\)。此时如果我们直接将这个数组映射回原数组，可以发现我们无法得到有效的区间。
所以，我们不可以这么直接的将前缀和数组映射回原数组，应该考虑这个经过离散化后的数组每一个值表示的都是一段区间。如果中间不存在零的出现，就说明这个映射区间是连续的，可以直接映射回去求区间长度即可（这个数组是有序的，如果是0，一定存在没有被覆盖到的地方）。
如果出现了间断，那么我们就应把数组中的每一个点拿出来单独考虑。如果是1，就说明这个端点（不难发现我们离散化之后获得的是很多个区间的端点）到下一个端点之间的区间是没有断点的，我们就可以把前缀和数组的这个端点单独拿出来考虑，映射回原数组体现出来的就是一个单独的小区间，不考虑与其它区间的关系，则有\(arr[i+1]-arr[i]\)可以作为有效区间被我们统计，之后再考虑下一个端点。如果是0，则为间断区间，跳过即可。
不难发现，题目作者为了简化问题，特地选取的开区间，不存在需要我们考虑可以取到右端点的两个间断区间。如果我们假设题目此时取到的为闭区间，则我们仍然需要以左闭右开的形式进行差分，避免选取中间的间断区间。
#include<bits/stdc++.h>
using namespace std;
const int N = 20200*2;
typedef pair<long long,long long>PII;
vector<long long>alls;
vector<PII>pos;
int n;
long long ans,sum;
int a[N],b[N];
int find(int x){
int l=-1,r=alls.size();
while(l+1!=r){
int mid=l+((r-l)>>1);
if(alls[mid]<x)l=mid;
else r=mid;
}
return r+1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
long long l,r;
scanf("%lld %lld",&l,&r);
alls.push_back(l);
alls.push_back(r);
pos.push_back({l,r});
}
sort(alls.begin(),alls.end());//映射操作
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重操作
for(auto item:pos){
int l=find(item.first),r=find(item.second);
a[l]=item.first,a[r]=item.second;
b[l]+=1,b[r]-=1;//b[l]+=1,b[r+1]-=1;
}
for (int i = 1; i <= alls.size(); i++) {
sum += b[i];//这个拿出去也一样
if (sum > 0) ans += a[i + 1] - a[i];
}
// for(int i=1;i<=alls.size()+1;i++){
// b[i]+=b[i-1];
// }
// for(int i=1;i<=alls.size();i++){
// cout<<b[i]<<' ';
// }cout<<endl;
// long long l,r;
// for(int i=1;i<=alls.size();i++){
// if(b[i]>0&&b[i-1]<=0)l=i;
// if(b[i]>0&&b[i+1]<=0){
// r=i;
// cout<<r<<' '<<l<<endl;
// ans+=a[r]-a[l]+1;
// }
// }
cout<<ans<<endl;
return 0;
}