HDU 3255 Farming

矩形面积并变形，一层一层的算体积

#include<cstdio>

#include<cstring>

#include<cmath>

#include<map>

#include<algorithm>

using namespace std;

const long long maxn=+;

struct Seg

{

    long long x;

    long long Y1,Y2;//离散化之后的坐标

    long long flag;

} s[maxn];

long long X1[maxn],X2[maxn],Y1[maxn],Y2[maxn],V[maxn];

long long p[],pp[];

map<long long ,long long>m;

long long M[maxn];

long long k;

long long n,tot,h;

long long sum,ans;

struct SegTree

{

    long long len;

    long long cover;

} segTree[maxn*];

bool cmp(const Seg&a,const Seg&b)

{

    return a.x<b.x;

}

void lsh()

{

    k=;

    m.clear();

    for(long long i=; i<=n; i++)

    {

        if(m[Y1[i]]==) M[k++]=Y1[i],m[Y1[i]]=;

        if(m[Y2[i]]==) M[k++]=Y2[i],m[Y2[i]]=;

    }

    sort(M,M+k);

    m.clear();

    for(long long i=; i<k; i++) m[M[i]]=i;

}

void build(long long l,long long r,long long rt)

{

    segTree[rt].cover=;

    segTree[rt].len=;

    if(l==r) return;

    long long m=(l+r)/;

    build(l,m,*rt);

    build(m+,r,*rt+);

}

void pushUp(long long rt,long long l,long long r)

{

    if(segTree[rt].cover) segTree[rt].len=M[r]-M[l-];

    else segTree[rt].len=segTree[*rt].len+segTree[*rt+].len;

}

void update(long long info,long long L,long long R,long long l,long long r,long long rt)

{

    if(L<=l&&r<=R)

    {

        segTree[rt].cover=segTree[rt].cover+info;

        pushUp(rt,l,r);

        return;

    }

    long long m=(l+r)/;

    if(L<=m) update(info,L,R,l,m,*rt);

    if(R>m)  update(info,L,R,m+,r,*rt+);

    pushUp(rt,l,r);

}

int main()

{

    long long T,zz=;

    scanf("%lld",&T);

    while(T--)

    {

        scanf("%lld%lld",&n,&h);

        p[]=;

        for(long long i=;i<=h;i++)

        {

            scanf("%lld",&p[i]);

            pp[i]=p[i];

        }

        sort(pp+,pp+h+);

        for(long long i=; i<=n; i++){

            scanf("%lld%lld%lld%lld%lld",&X1[i],&Y1[i],&X2[i],&Y2[i],&V[i]);

            V[i]=p[V[i]];

        }

        lsh();

        long long Ans=;

        for(long long r=; r<=h; r++)

        {

            tot=;

            for(long long i=; i<=n; i++)

            {

                if(V[i]>=pp[r])

                {

                    s[tot].x=X1[i],s[tot].Y1=m[Y1[i]],s[tot].Y2=m[Y2[i]],s[tot].flag=,tot++;

                    s[tot].x=X2[i],s[tot].Y1=m[Y1[i]],s[tot].Y2=m[Y2[i]],s[tot].flag=-,tot++;

                }

            }

            sort(s,s+tot,cmp);

            ans=;

            build(,k,);

            for(long long i=; i<tot; i++)

            {

                sum=segTree[].len;

                ans=ans+sum*(s[i].x-s[i-].x);

                update(s[i].flag,s[i].Y1+,s[i].Y2,,k,);

            }

            Ans=Ans+ans*(pp[r]-pp[r-]);

        }

        printf("Case %lld: ",zz++);

        printf("%lld\n",Ans);

    }

    return ;

}