hdu 3255 Farming 线段树空间体积

刚刚敲完空间体积相交，但是这道题竟然一开始没有思路，果然还是该打，总结线段树的做题经验就是要仔细看数据的范围。

解题思路：

因为每一种植物的价值最大不过到100，那么我们需要的价值就是面积*价值，那么我们何不把价值作为第三个坐标轴z轴栏运算呢~

接下来不说了，，看代码

View Code

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<algorithm>
  4 #include<string.h>
  5 using std::unique;
  6 using std::sort;
  7 const int N = 30005;
  8 struct Re
  9 {
 10        int x1,x2,y1,y2,z1,z2;
 11 }Re[N];
 12 struct line
 13 {
 14        int y,x1,x2,s;
 15        bool operator < (const line & tmp)const
 16        {
 17            return y<tmp.y;
 18        }
 19 }Line[N<<2];
 20 int Z[N<<2],X[N<<3],cover[N<<3],Price[N<<2];
 21 __int64 sum[N<<3];
 22 int Fin(int k,int len)
 23 {
 24     int l=0,r=len;
 25     while(l<r)
 26     {
 27         int m=(l+r)>>1;
 28         if(X[m]==k)return m;
 29         if(X[m]>k)r=m-1;
 30         else l=m+1;
 31     }
 32     return l;
 33 }
 34 void PushUp(int t,int l,int r)
 35 {
 36      if(cover[t]>0)sum[t]=(__int64)(X[r+1]-X[l]);
 37      else
 38        if(l==r)sum[t]=0;
 39        else  sum[t]=sum[t<<1]+sum[t<<1|1];
 40 }
 41 void update(int t,int l,int r,int L,int R,int val)
 42 {
 43      if(L<=l&&r<=R)
 44      {
 45         cover[t]+=val;
 46         PushUp(t,l,r);
 47         return ;
 48      }
 49      int m=(r+l)>>1;
 50      if(L<=m)update(t<<1,l,m,L,R,val);
 51      if(R>m)update(t<<1|1,m+1,r,L,R,val);
 52      PushUp(t,l,r);
 53 }
 54 int main()
 55 {
 56     int t,n,m,k,T=0;
 57     scanf("%d",&t);
 58     while(t--)
 59     {
 60           scanf("%d%d",&n,&m);
 61           int topz=0;
 62           Z[topz++]=0;
 63           for(int i=1;i<=m;i++){scanf("%d",&Price[i]);Z[topz++]=Price[i];}
 64           for(int i=0;i<n;i++)
 65           {
 66               scanf("%d%d%d%d%d",&Re[i].x1,&Re[i].y1,&Re[i].x2,&Re[i].y2,&k);
 67               Re[i].z1=0,Re[i].z2=Price[k];
 68           }
 69           sort(Z,Z+topz);
 70           topz=unique(Z,Z+topz)-Z;
 71           __int64 ans=0;
 72           for(int i=0;i<topz-1;i++)
 73           {
 74               int topx=0,topl=0;
 75               for(int j=0;j<n;j++)
 76               {
 77                   if(Re[j].z1<=Z[i]&&Re[j].z2>Z[i])
 78                   {
 79                       Line[topl].y=Re[j].y1;Line[topl].x1=Re[j].x1;Line[topl].x2=Re[j].x2;Line[topl].s=1;topl++;
 80                       Line[topl].y=Re[j].y2;Line[topl].x1=Re[j].x1;Line[topl].x2=Re[j].x2;Line[topl].s=-1;topl++;
 81                       X[topx++]=Re[j].x1;X[topx++]=Re[j].x2;
 82                   }
 83               }
 84               sort(X,X+topx);
 85               sort(Line,Line+topl);
 86               topx=unique(X,X+topx)-X;
 87               memset(sum,0,sizeof(sum));
 88               memset(cover,0,sizeof(cover));
 89               __int64 ret=0;
 90               for(int j=0;j<topl-1;j++)
 91               {
 92                   int l=Fin(Line[j].x1,topx-1);
 93                   int r=Fin(Line[j].x2,topx-1)-1;
 94                   if(l<=r)update(1,0,topx-1,l,r,Line[j].s);
 95                   ret+=(sum[1]*(__int64)(Line[j+1].y-Line[j].y));
 96               }
 97               ans+=ret*(__int64)(Z[i+1]-Z[i]);
 98           }
 99           printf("Case %d: %I64d\n",++T,ans);
100     }
101     return 0;
102 }