FarmingTime Limit: 12000/6000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1445Accepted Submission(s): 428
Problem Description
You have a big farm, and you want to grow vegetables in it. You’re too lazy to seed the seeds yourself, so you’ve hired n people to do the job for you.Each person works in a rectangular piece of land, seeding one seed in one unit square. The working areas of different people may overlap, so one unit square can be seeded several times. However, due to limited space, different seeds in one square fight each other — finally, the most powerful seed wins. If there are several "most powerful" seeds, one of them win (it does not matter which one wins).There are m kinds of seeds. Different seeds grow up into different vegetables and sells for different prices.As a rule, more powerful seeds always grow up into more expensive vegetables.Your task is to calculate how much money will you get, by selling all the vegetables in the whole farm.
Input
The first line contains a single integer T (T <= 10), the number of test cases.Each case begins with two integers n, m (1 <= n <= 30000, 1 <= m <= 3).The next line contains m distinct positive integers pi (1 <= pi <= 100), the prices of each kind of vegetable.The vegetables (and their corresponding seeds) are numbered 1 to m in the order they appear in the input.Each of the following n lines contains five integers x1, y1, x2, y2, s, indicating a working seeded a rectangular area with lower-left corner (x1,y1), upper-right corner (x2,y2), with the s-th kind of seed.All of x1, y1, x2, y2 will be no larger than 106 in their absolute values.
Output
For each test case, print the case number and your final income.
Sample Input
21 1250 0 10 10 12 25 20 0 2 1 11 0 3 2 2
Sample Output
Case 1: 2500Case 2: 16
Source
2009 Asia Regional Ningbo Online
Recommend
wujianhua|We have carefully selected several similar problems for you:32543251325232533256
题意：
原始题意就不说了。抽象出来就是给你n个底面在xoy平面与坐标轴平行的立方体。他们之间可以重叠。问体积并是多少。
思路：
和求面积并的思路类似。用高度（价值）把立方体分成很多段。然后一段一段求体积就好。
详细见代码：
#include<cstdio>#include<algorithm>#include<iostream>using namespace std;const int maxn=30010;typedef long long ll;#define lson L,mid,ls#define rson mid+1,R,rsstruct node{int x1,x2,h,tag;//面积并用的值。tag表示加边还是减边int p;//存第三维高度。node(){}node(int a,int b,int c,int d,int e):x1(a),x2(b),h(c),tag(d),p(e){}bool operator <(const node &op) const{return h<op.h;}} seg[maxn<<1],tmp[maxn<<1];int val[maxn],H[maxn<<1];int len[maxn<<3],cov[maxn<<3];void build(int L,int R,int rt){cov[rt]=len[rt]=0;if(L==R)return;int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;build(lson);build(rson);}void update(int L,int R,int rt,int l,int r,int d){if(l<=L&&R<=r){cov[rt]+=d;len[rt]=cov[rt]?H[R+1]-H[L]:(L==R?0:len[rt<<1]+len[rt<<1|1]);//printf("%d -> %d len %d\n",H[L],H[R+1],len[rt]);return;}int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;if(l<=mid)update(lson,l,r,d);if(r>mid)update(rson,l,r,d);len[rt]=cov[rt]?H[R+1]-H[L]:len[ls]+len[rs];//printf("%d -> %d len %d\n",H[L],H[R+1],len[rt]);}int main(){int t,n,m,i,j,cas=1,ct,cnt;int x1,x2,y1,y2,ch,ns;ll ans,tp;scanf("%d",&t);while(t–){scanf("%d%d",&n,&m);for(i=1;i<=m;i++)scanf("%d",&val[i]);ans=ns=ct=0;for(i=1;i<=n;i++){scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&ch);seg[ns++]=node(x1,x2,y1,1,val[ch]);seg[ns++]=node(x1,x2,y2,-1,val[ch]);H[ct++]=x1,H[ct++]=x2;}sort(H,H+ct);ct=unique(H,H+ct)-H;sort(seg,seg+ns);sort(val+1,val+m+1);for(i=0;i<m;i++){for(j=cnt=0;j<ns;j++)if(seg[j].p>val[i])tmp[cnt++]=seg[j];build(0,ct-2,1);for(j=tp=0,cnt–;j<cnt;j++){int l=lower_bound(H,H+ct,tmp[j].x1)-H;int r=lower_bound(H,H+ct,tmp[j].x2)-H-1;update(0,ct-2,1,l,r,tmp[j].tag);tp+=(ll)len[1]*(tmp[j+1].h-tmp[j].h);//注意ll.算面积并}ans+=tp*(val[i+1]-val[i]);//面积乘高就是体积了。}printf("Case %d: %I64d\n",cas++,ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，不是每一次努力都有收获，但是，每一次收获都必须经过努力。
