hdu 3255 体积并

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("!\n")

#define MAXN 160000+5

#define MAX(a,b) a>b?a:b

#define blank pf("\n")

#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<<],len[MAXN<<];

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<<],tmp[MAXN<<];

void PushUp(int rt,int l,int r)

{

    if(col[rt])

    {

        len[rt] = hh[r+] - hh[l];

    }

    else if(l==r) len[rt] = ;

    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)>>;

    if(L <= mid) update(val,L,R,l,mid,ls);

    if(R > mid) update(val,L,R,mid+,r,rs);

    PushUp(rt,l,r);

}

int main()

{

    int n,i,j,t,kase=;

    double ans;

    sf("%d",&t);

    while(t--)

    {

        sf("%d%d",&n,&m);

        int v=;

        for(i=;i<=m;i++)

        sf("%d",&V[i]);

        for(i=;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,,V[r]);

            hh[++v]=y2;

            a[v]=node(y1,y2,x2,-,V[r]);

        }

        sort(hh+,hh++v);

        sort(a+,a++v);

        int d=;

        for(i=;i<=v;i++)

            if(hh[i]!=hh[i-])

                hh[++d]=hh[i];

        double ans=;

        V[]=;

        sort(V,V+m+);

        int ct =;

        for(j=;j<=m;j++)

        {

            ct=;

            for(i=;i<=v;i++)

                if(a[i].v>V[j-])

                    tmp[ct++]=a[i];

            mem(col,);

            mem(len,);

            for(i=;i<ct-;i++)

            {

                //int l=BinarySearch(tmp[i].l,1,M);

                //int r=BinarySearch(tmp[i].r,1,M)-1;

                int l = lower_bound(hh+,hh+d,tmp[i].l)-hh;

                int r = lower_bound(hh+,hh+d,tmp[i].r)-hh-;

                if(l<=r) update(tmp[i].c,l,r,,d,);

                ans+=len[]*(double)(V[j]-V[j-])*(tmp[i+].x-tmp[i].x);

            }

        }

        pf("Case %d: %.0lf\n",kase++,ans);

    }

    return ;

}