文章

0

粉丝

5

获赞

39

访问

20427

头像
差分数组
Sacan SVIP
P1175
发布于2022年6月11日 12:15
阅读数 667

频繁修改区间。如果修改次数和范围较大,无脑暴力可能会超时,这时候就需要差分数组,快速修改区间值

#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;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发