题意：在一块地上种蔬菜，每种蔬菜有个价值。对于同一块地蔬菜价值高的一定是最后存活，求最后的蔬菜总值。
思路：将蔬菜的价值看做高度的话，题目就转化成求体积并，这样就容易了。
与HDU 3642 Get The Treasury 同样求体积并，只不过HDU 3642 是要求覆盖大于等于3次的体积并，该题比那道题容易些。
先将蔬菜价值（即高度）从小到大排序，然后一层一层地开始扫描，计算每层中的面积并，这个就同二维扫描一样。
然后再用面积乘以这层的高度，即得到该层的体积并。然后所有层的体积加起来，即为所求。
一开始RE。。。
后来仔细看了代码，再看看题意，发现x,y的绝对值小于10^6，也就是有可能为负数，而原本建立了一个数组hashx，
建立x坐标到离散值的映射，之所以RE是因为x<0的话下标就越界了。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid,R using namespace std;
const int maxn=;
int n,m;
int xval[maxn<<]; //存储x坐标
//int hashx[1000005]; //建立横坐标——离散值的映射，一开始没注意题目中说明：x,y的绝对值小于10^6，也就是有可能为负数，不能用hashx
int hashkey[maxn<<]; //建立离散值——坐标的映射，然后用二分搜索对应的离散值
int idx,hidx; //idx为xval数组的下标，hidx用于x坐标的离散化
int price[]; //蔬菜价格 struct Line{
int l,r,y;
int tp; //标记矩形的上边界(tp=-1)和下边界(tp=1)
int hight; //hight为该区域种的蔬菜价值，表示该线条所处的高度范围，0~hight
bool operator<(const Line tmp)const{
return y<tmp.y;
}
}line[maxn<<]; struct Node{
int cnt;
long long sum;
long long len;
}tree[maxn<<]; void build(int rt,int L,int R){
tree[rt].cnt=;
tree[rt].len=hashkey[R]-hashkey[L];
tree[rt].sum=;
if(L+==R)
return;
int mid=(L+R)>>;
build(lson);
build(rson);
}
void pushUp(int rt,int L,int R){
if(tree[rt].cnt){
tree[rt].sum=tree[rt].len;
}
else{
if(L+==R){
tree[rt].sum=;
}
else{
tree[rt].sum=tree[rt<<].sum+tree[rt<<|].sum;
}
}
}
void update(int rt,int L,int R,int l,int r,int c){
if(l<=L&&R<=r){
tree[rt].cnt+=c;
pushUp(rt,L,R);
return;
}
int mid=(L+R)>>;
if(l<mid)
update(lson,l,r,c);
if(r>mid)
update(rson,l,r,c); /*
if(r<=mid)
update(lson,l,r,c);
else if(l>=mid)
update(rson,l,r,c);
else{
update(lson,l,mid,c);
update(rson,mid,r,c);
}
*/
pushUp(rt,L,R);
}
int binarySearch(int m){
int l=,r=hidx+,mid;
while(r-l>){
mid=(l+r)>>;
if(hashkey[mid]<=m)
l=mid;
else
r=mid;
}
return l;
}
int main()
{
int t;
int x1,y1,x2,y2,s;
scanf("%d",&t);
for(int q=;q<=t;q++){
scanf("%d%d",&n,&m);
memset(price,,sizeof(price));
for(int i=;i<=m;i++){
scanf("%d",&price[i]);
}
idx=-;
for(int i=;i<=n;i++){
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&s);
line[*i-].l=x1;line[*i-].r=x2;line[*i-].y=y1;line[*i-].hight=price[s];line[*i-].tp=;
line[*i].l=x1;line[*i].r=x2;line[*i].y=y2;line[*i].hight=price[s];line[*i].tp=-;
xval[++idx]=x1;
xval[++idx]=x2;
}
n*=;
sort(line+,line+n+);
sort(xval,xval+idx+);
hidx=;
//hashx[xval[0]]=hidx;
hashkey[hidx]=xval[];
for(int i=;i<=idx;i++){
if(xval[i]!=xval[i-]){
//hashx[xval[i]]=++hidx; xval[i]有可能为负数啊！！！所以才导致RE。。。
hashkey[++hidx]=xval[i];
}
} long long ans=;
int a,b;
sort(price+,price+m+);
long long sum=;
//枚举每一层
for(int w=;w<=m;w++){
int last=;
long long s=; //该层的面积
build(,,hidx); //是在这里build，一开始写在外层循环外面了。。。
for(int i=;i<=n;i++){
if(line[i].hight>=price[w]){
s+=tree[].sum*(line[i].y-line[last].y);
a=binarySearch(line[i].l);
b=binarySearch(line[i].r);
update(,,hidx,a,b,line[i].tp);
last=i;
}
}
sum+=s*(price[w]-price[w-]); //该层的体积
} printf("Case %d: %I64d\n",q,sum);
}
return ;
}