题解 AT1011 【AtColor】差分
jijidawang
2020-06-26 13:28:21
$n^2$ 肯定过不了百万所以差分裸题啊
差分的思路就是维护一个差分数组 $s$，每次 $[l,r]$ 区间覆盖就用 $s_l=s_l+1$，$s_{r+1}=s_{r+1}-1$。
对于 $s$ 做前缀和即可精准定位一个点的区间个数。
原理大概是前缀和中 $s_l$ 加了一后面全都加一了，$s_{r+1}$ 减一了就把后面全减一了导致 $[l,r]$ 全体加一的效果。
变成线性复杂度就肯定能过了。
Code:
```cpp
#include<iostream>
using namespace std;
const int N=1000005;
int s[N],l,r,n,sum,ans,maxnum;
int main()
{
cin>>n;
for (int i=0;i<n;i++)
{
cin>>l>>r;
++s[l]; --s[r+1]; // 差分操作
maxnum=max(maxnum,r+1); // 提前求出最大值使得不用求太多 max，这步优化可以不加，看数据范围能过
}
for (int i=0;i<=maxnum;i++){sum+=s[i]; ans=max(ans,sum);} // 对每个点的区间个数求 max
cout<<ans;
return 0;
}
```