差分数组是啥？
我也不是很清楚，大概就是一个数组吧！
b战上有很多讲解的视频，我写下我学到的。
差分数组就是，原本有个数组，然后你要修改某个区间的数值，
正常人会想到遍历去修改，这是没错的，但吃力不讨好。
用差分数组可以很快搞定。
例如：
有一个全为0的数组a，把区间【2，5】上的值修改为1，只需要让a[2]=1,a[6]=-1,
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[10]={0};
//构造差分数组
a[2]=1;
a[6]=-1;
int ans=0;
for(int i=0;i<10;i++)
{
ans+=a[i];//修改后的数组第i项等于差分数组前i项的和
cout<<ans<<" ";
}
}
例题：
问题 I: Ensemble’s heritage
题目描述
作为十三课的卢卡，是没有权力去直接审讯犯人的。所以卢卡就偷到了N张卡，监狱一共有M个房间。
第i个监狱的门可以由 第L---R张卡打开
但是卢卡的数学并不好，他想让你帮帮他，有几张卡能打开所有的门
输入
N M
L1 R1
L2 R2
L3 R3
...
输出
要输出的
样例输入 复制
4 2
1 3
2 4
样例输出 复制
2
提示
1<=N<=1e5
1<=M<=1e5
1<=Li<=Ri<=N
#include<bits/stdc++.h>
using namespace std;
int s[101010];
int main()
{
int n,m;
cin>>n>>m;
//把能打开的位置加上1
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
s[l]++;
s[r+1]--;
}
int ans=0;
//如果该位置上有m个钥匙能打开，则结果加一
for(int i=1;i<=n;i++)
{
s[i]+=s[i-1];
if(s[i]==m)
ans++;
}
cout<<ans;
}
刚开始不会写，后来看了学长的，他用了差分数组，我心想差分数组是什么鬼？？
然后上b战了，链接：
"差分"的介绍与使用方法_哔哩哔哩_bilibili
当然了，这里不用差分数组也可以写出来：我们用一个结构体来储存每个房间的左和右：
struct info{
int l;
int r;
}a[100005];
然后按照a[i].l 递增排序,再遍历这个结构体数组，找到最小的a[i].r，
再用最大的a[i].l减去这个最小的a[i].r就是答案辣（记得要加一）
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct info{
int l=0;
int r=0;
}a[100005];
bool mysort(info a,info b)
{
return a.l<b.l;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
cin>>a[i].l>>a[i].r;
sort(a,a+m,mysort);
int min=1000005;
for(int i=0;i<m;i++)
{
if(a[i].r<min)
min=a[i].r;
}
int ans=min-a[m-1].l+1;
if(ans<0)
cout<<0<<endl;
else
cout<<ans<<endl;
}
