【题目描述】
你可能已经听说了金发姑娘和3只熊的经典故事。
鲜为人知的是，金发姑娘最终经营了一个农场。在她的农场，她有一个谷仓含N头奶牛（1<=N <= 20000)。不幸的是，她的奶牛对温度相当敏感。
第i头奶牛必须在指定的温度范围内A(i)..B(i)才感觉舒适；（0<=A(i)<=B(i)<= 1,000,000,000）。如果金发姑娘在谷仓放置一个温控器；如果温度T<A(i)，牛会太冷，并将产生x单位牛奶。如果她把恒温器调到（A(i)<=T<=B(i)）这个范围内,那么牛会感到舒适，并将产生Y单位牛奶。如果她把恒温器调到温度T>B(i)，牛会感觉很热，并将产生的Z单位牛奶。正如预期的那样，Y的值总是大于X和Z。
给定的X，Y，和Z，以及每个牛的温度的最佳范围，如果金发姑娘设置谷仓的温控器最佳，请计算金发姑娘得到牛奶的最大数量，已知X，Y和Z都是整数，范围0..1000。温控器可以设置为任意整数的值。
【输入格式】
第1行：四个用空格隔开的整数：N X Y Z。
第2行..1 + N：行1+i包含两个用空格隔开的整数：A(i)和B(i)。
【输出格式】
1行：金发姑娘最多可以获得的牛奶，当她在谷仓的最佳温度设定。
【样例输入】
4 7 9 6 5 8 3 4 13 20 7 10
【样例输出】
31
【提示】
在农场里有4头奶牛，温度范围5..8，3..4，13..20，10..7。一个寒冷的奶牛生产7单位的牛奶，一个舒适的奶牛生产9个单位的牛奶，一个热牛生产6单位牛奶。
【数据规模】
50%的测试数据：n<=5
其余50%的测试数据：10000<n<=20000.
【来源】
USACO 2013 November Contest, Bronze
translate by cqw
data from cstdio
题解：将左右端点离散化 用三个数组差分 分别维护小于 在区间里 大于 的数量 计算答案
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=50000+10;
int a[maxn],b[maxn],c[maxn];
struct T{int l,r;
}A[maxn];
int hash[maxn];
int B[maxn];
int tot=0,to=0;
inline int bs(int x){int l=1,r=tot;while(l+1<r){int mid=(l+r)>>1;if(hash[mid]>=x)r=mid;else l=mid+1;}if(hash[l]==x)return l;return r;
}
int main(){freopen("milktemp.in","r",stdin);freopen("milktemp.out","w",stdout);int n,x,y,z;scanf("%d %d %d %d",&n,&x,&y,&z);for(int i=1;i<=n;i++){scanf("%d %d",&A[i].l,&A[i].r);B[++to]=A[i].l;B[++to]=A[i].r;}sort(B+1,B+to+1);hash[++tot]=B[1];for(int i=2;i<=to;i++)if(B[i]!=B[i-1])hash[++tot]=B[i];for(int i=1;i<=n;i++){int u=bs(A[i].l);a[u]--;b[u]++;u=bs(A[i].r);b[u+1]--;c[u+1]++;}int xnum=n,ynum=0,znum=0;int ans=0;for(int i=1;i<=tot;i++){xnum+=a[i];ynum+=b[i];znum+=c[i];ans=max(ans,xnum*x+ynum*y+znum*z);}printf("%d\n",ans);
return 0;
}