http://www.cnblogs.com/kane0526/archive/2013/03/07/2948446.html
http://blog.csdn.net/acdreamers/article/details/11854781
每块蔬菜地种植蔬菜收获的利润为 val=x*y*price。 面积乘以价格，题目的重点转换在于如何确定重叠区域怎么让它种植最贵的蔬菜。
观察利润计算公式 : x*y*price <==> x*y*h 可以转换为求体积并。
体积并其实和面积并基本一样，将体积的范围记录下来，每一层遍历求面积并，结果就是底面积乘每一层的高之和
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 160000+5 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f #define ls (rt<<1) #define rs (rt<<1|1) int n,m; double hh[MAXN],col[MAXN<<3],len[MAXN<<3]; int V[MAXN]; struct node { double l,r,x,c; int v; node(){} node(double a,double b,double c,double d,int e):l(a),r(b),x(c),c(d),v(e){} bool operator < (const node &b) const { return x<b.x; } }a[MAXN<<3],tmp[MAXN<<3]; void PushUp(int rt,int l,int r) { if(col[rt]) { len[rt] = hh[r+1] - hh[l]; } else if(l==r) len[rt] = 0; else { len[rt] = len[ls]+len[rs]; } } void update(int val,int L,int R,int l,int r,int rt) { if(L<=l && r<=R) { col[rt] += val; PushUp(rt,l,r); return; } int mid = (l+r)>>1; if(L <= mid) update(val,L,R,l,mid,ls); if(R > mid) update(val,L,R,mid+1,r,rs); PushUp(rt,l,r); } int main() { int n,i,j,t,kase=1; double ans; sf("%d",&t); while(t--) { sf("%d%d",&n,&m); int v=0; for(i=1;i<=m;i++) sf("%d",&V[i]); for(i=1;i<=n;i++) { double x1,x2,y1,y2; int r; sf("%lf%lf%lf%lf%d",&x1,&y1,&x2,&y2,&r); hh[++v]=y1; a[v]=node(y1,y2,x1,1,V[r]); hh[++v]=y2; a[v]=node(y1,y2,x2,-1,V[r]); } sort(hh+1,hh+1+v); sort(a+1,a+1+v); int d=1; for(i=2;i<=v;i++) if(hh[i]!=hh[i-1]) hh[++d]=hh[i]; double ans=0; V[0]=0; sort(V,V+m+1); int ct =0; for(j=1;j<=m;j++) { ct=0; for(i=1;i<=v;i++) if(a[i].v>V[j-1]) tmp[ct++]=a[i]; mem(col,0); mem(len,0); for(i=0;i<ct-1;i++) { //int l=BinarySearch(tmp[i].l,1,M); //int r=BinarySearch(tmp[i].r,1,M)-1; int l = lower_bound(hh+1,hh+d,tmp[i].l)-hh; int r = lower_bound(hh+1,hh+d,tmp[i].r)-hh-1; if(l<=r) update(tmp[i].c,l,r,1,d,1); ans+=len[1]*(double)(V[j]-V[j-1])*(tmp[i+1].x-tmp[i].x); } } pf("Case %d: %.0lf ",kase++,ans); } return 0; }