AcWing 1952. 差分
原题链接
简单
作者:
cyzh
,
2022-01-13 23:47:47
,
所有人可见
,
阅读 517
对3个区间进行差分就行
区间1:(最小的数, A - 1]
区间2:[A, B]
区间3:[B + 1, 最大的数)
A,B在0 ~ 1e9, 这里最小数我取 -1, 最大取 2e9
对区间[A, B] 差分 mp[A] +, mp[B + 1] -
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, a, b, c; cin >> n >> a >> b >> c;
map<int, int> mp;
for(int i = 0; i < n; i++){
int k1, k2; cin >> k1 >> k2;
//(-1 ~ k1 - 1] , [k1 ,k2] , [k2 + 1 ~ 2e9),
mp[-1] += a, mp[k1 - 1 + 1] -= a;
mp[k1] += b, mp[k2 + 1] -= b;
mp[k2 + 1] += c, mp[2e9] -= c;
}
int sum = 0, ans = 0;
for(auto [k, v] : mp){
sum += v;
ans = max(ans, sum);
}
cout << ans << endl;
return 0;
}