文章
28
粉丝
226
获赞
53
访问
143.8k
频繁修改区间。如果修改次数和范围较大,无脑暴力可能会超时,这时候就需要差分数组,快速修改区间值
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int L,M;
while(cin >> L >> M){
// [1, L+1]是树
vector<int> arr(L+3, 1);
arr[0] = 0;
arr[L+2] = 0;
vector<int> d(L+3, 0);
d[1] = 1;
d[L+2] = -1;
for(int i = 1;i <= M;i++){
int l,r;
cin >> l >> r;
l += 1;
r += 1;
d[l] = d[l] - 1;
d[r+1] = d[r+1] + 1;
}
// 恢复。d[i] = arr[i] - arr[i-1]
for(int i = 1;i <= L+1;i++){
arr[i] = d[i] + arr[i-1];
}
int cnt = 0;
for(int i = 1;i <= L+1;i++){
if(arr[i] > 0){
cnt += arr[i];
}
}
cout << cnt << endl;
}
return 0;
}
登录后发布评论
您