|
题目描述
有编号为0到M 的（M+1）个格子，现在有N个操作 （x，y），表示将从x 到 y的格子染色，问一共有多少个格子被染色。
输入
第一行两个整数，分别表示N和M。
接下来有N行，每行两个整数，分别表示x和y。
输出
输出一个整数，表示有多少个格子被染色。
样例输入?Copy
3 10
0 5
2 6
8 9
样例输出?Copy
9
提示
30%的数据满足N，M<=10000
100%的数据满足N,M<=1000000;任何操作保证0<=x<=y<=M。
思路：
直接暴力时间复杂度为O(n*m),将涂色视为区间加值，用差分数组
#include <iostream>
using namespace std;
int a[1000005],sum[1000005];//a[]差分数组，sum[]前缀和数组
int main()
{
int m,n,ans=0;
scanf("%d%d",&n,&m);
while(n--)
{
int l,r;
scanf("%d%d",&l,&r);
a[l+1]++,a[r+2]--;
}
for(int i=1;i<=m+1;i++)
sum[i]=sum[i-1]+a[i];
for(int i=1;i<=m+1;i++)
if(sum[i]) ans++;
printf("%d",ans);
return 0;
}
对于数组arr[],对其(l,r)区间的数加上v，对其差分数组d[] d[l]+v,d[r+1]-v;
差分数组的构造：?
d[1]=arr[1],d[i]=arr[i]-arr[i-1]
|