题意：在一块地上种蔬菜，每种蔬菜有个价值。对于同一块地蔬菜价值高的一定是最后存活，求最后的蔬菜总值。
思路：将蔬菜的价值看做高度的话，题目就转化成求体积并，这样就容易了。
与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=30005; int n,m; int xval[maxn<<1]; //存储x坐标 //int hashx[1000005]; //建立横坐标——离散值的映射，一开始没注意题目中说明：x,y的绝对值小于10^6，也就是有可能为负数，不能用hashx int hashkey[maxn<<1]; //建立离散值——坐标的映射，然后用二分搜索对应的离散值 int idx,hidx; //idx为xval数组的下标，hidx用于x坐标的离散化 int price[5]; //蔬菜价格 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<<1]; struct Node{ int cnt; long long sum; long long len; }tree[maxn<<3]; void build(int rt,int L,int R){ tree[rt].cnt=0; tree[rt].len=hashkey[R]-hashkey[L]; tree[rt].sum=0; if(L+1==R) return; int mid=(L+R)>>1; 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+1==R){ tree[rt].sum=0; } else{ tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].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)>>1; 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=0,r=hidx+1,mid; while(r-l>1){ mid=(l+r)>>1; 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=1;q<=t;q++){ scanf("%d%d",&n,&m); memset(price,0,sizeof(price)); for(int i=1;i<=m;i++){ scanf("%d",&price[i]); } idx=-1; for(int i=1;i<=n;i++){ scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&s); line[2*i-1].l=x1;line[2*i-1].r=x2;line[2*i-1].y=y1;line[2*i-1].hight=price[s];line[2*i-1].tp=1; line[2*i].l=x1;line[2*i].r=x2;line[2*i].y=y2;line[2*i].hight=price[s];line[2*i].tp=-1; xval[++idx]=x1; xval[++idx]=x2; } n*=2; sort(line+1,line+n+1); sort(xval,xval+idx+1); hidx=1; //hashx[xval[0]]=hidx; hashkey[hidx]=xval[0]; for(int i=1;i<=idx;i++){ if(xval[i]!=xval[i-1]){ //hashx[xval[i]]=++hidx; xval[i]有可能为负数啊！！！所以才导致RE。。。 hashkey[++hidx]=xval[i]; } } long long ans=0; int a,b; sort(price+1,price+m+1); long long sum=0; //枚举每一层 for(int w=1;w<=m;w++){ int last=0; long long s=0; //该层的面积 build(1,1,hidx); //是在这里build，一开始写在外层循环外面了。。。 for(int i=1;i<=n;i++){ if(line[i].hight>=price[w]){ s+=tree[1].sum*(line[i].y-line[last].y); a=binarySearch(line[i].l); b=binarySearch(line[i].r); update(1,1,hidx,a,b,line[i].tp); last=i; } } sum+=s*(price[w]-price[w-1]); //该层的体积 } printf("Case %d: %I64d ",q,sum); } return 0; }