AcWing 1952. 金发姑娘和 N 头牛（差分，离散化）

AcWing 1952. 金发姑娘和 N 头牛（差分，离散化）

【题目描述】
你可能听过关于金发姑娘和三只熊的经典故事。
然而，鲜为人知的是，金发姑娘最终成了一个农民。
在她的农场中，她的牛棚里有 N N N头奶牛。
不幸的是，她的奶牛对温度相当敏感。
对于奶牛 i i i，使其感到舒适的温度为 A i … B i A_idots B_i Ai​…Bi​。
如果金发姑娘将牛棚的恒温器的温度 T T T设置为 T < A i TT 如果她将恒温器的温度 T T T设置在 A i ≤ T ≤ B i A_i≤T≤B_i Ai​≤T≤Bi​，奶牛就会感到舒适，并会产出 Y Y Y单位的牛奶。
如果她将恒温器的温度 T T T设置为 T > B i T>B_i T>Bi​，奶牛就会觉得热，并会产出 Z Z Z单位的牛奶。
正如所期望的那样， Y Y Y的值始终大于 X X X和 Z Z Z。
给定 X , Y , Z X,Y,Z X,Y,Z以及每头奶牛感到舒适的温度范围，请计算通过合理设定恒温器温度，金发姑娘可获得的最大产奶量。
恒温器温度可设置为任何整数。

【输入格式】
第一行包含四个整数 N , X , Y , Z N,X,Y,Z N,X,Y,Z。
接下来 N N N行，每行包含两个整数 A i A_i Ai​和 B i B_i Bi​。

【输出格式】
输出可获得的最大产奶量。

【数据范围】
1 ≤ N ≤ 20000 1≤N≤20000 1≤N≤20000
0 ≤ X , Y , Z ≤ 1000 0≤X,Y,Z≤1000 0≤X,Y,Z≤1000
0 ≤ A i ≤ B i ≤ 1 0 9 0≤A_i≤B_i≤10^9 0≤Ai​≤Bi​≤109

【输入样例】

4 7 9 6
5 8
3 4
13 20
7 10

【输出样例】

31

【样例解释】
金发姑娘可以将恒温器温度设置为 7 7 7或 8 8 8，这样会让奶牛 1 1 1和 4 4 4感到舒适，奶牛 2 2 2感到热，奶牛 3 3 3感到冷。
共可获得 31 31 31单位牛奶。

【分析】

---

题意为给定 N N N个区间 [ l , r ] [l,r] [l,r]，区间内部的每个点加上 Y Y Y，区间左部的每个点加上 X X X，区间右部的每个点加上 Z Z Z，因此可以使用差分的思想求解，本题区间下标范围很大，因此需要用到离散化，本题分别使用 m a p map map实现离散化与手写实现离散化进行求解。

---

【map实现离散化代码】

#include 
#include 
#include 
#include 

【手写实现离散化代码】

#include 
#include 
#include 
#include 
using namespace std;

const int N = 20010, INF = 2e9;
int l[N], r[N], b[N << 1];
int n, x, y, z;
vector xs;

int find(int v)
{
    //return lower_bound(xs.begin(), xs.end(), v) - xs.begin();
    int l = 0, r = xs.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (xs[mid] >= v) r = mid;
        else l = mid + 1;
    }
    return r;
}

int main()
{
    cin >> n >> x >> y >> z;
    for (int i = 0; i < n; i++)
    {
        cin >> l[i] >> r[i];
        xs.push_back(l[i]), xs.push_back(r[i] + 1);
    }
    xs.push_back(-INF), xs.push_back(INF);
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    for (int i = 0; i < n; i++)
    {
        int L = find(l[i]), R = find(r[i] + 1);
        b[0] += x, b[L] += y - x, b[R] += z - y, b[xs.size() - 1] -= z;
    }
    int res = 0, sum = 0;
    for (int i = 0; i < xs.size(); i++) sum += b[i], res = max(res, sum);
    cout << res << endl;
    return 0;
}