[线段树] hdu 3255 Farming#求体积并

/**
[线段树] hdu 3255 Farming#求体积并
扫描水平面，每次用求面积并的方法求每一个水平面的面积并，累加统计
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define N 66666
#define L(id) (id << 1)
#define R(id) (id << 1 | 1)
int n,m,pri[N];
int dy[N],cnt;
struct _st
{
    int l,r,sum,cnt;
    int mid()
    {
        return (l + r) >> 1;
    }
}st[N<<2];

struct _cube
{
    int x1,y1,x2,y2,h;
    void input()
    {
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h);
        dy[cnt++] = y1;
        dy[cnt++] = y2;
        h = pri[h];
    }
}cube[N];
struct _seg
{
    int x,y1,y2,flag;
    _seg(int a = 0,int b = 0,int c = 0,int d = 0)
    {
        x = a;
        y1 = b;
        y2 = c;
        flag = d;
    }
}sg[N];
bool cmp(_seg a,_seg b)
{
    return a.x < b.x;
}
void build(int id,int l,int r)
{
    st[id].l = l;
    st[id].r = r;
    st[id].cnt = st[id].sum = 0;
    if(l == r - 1)
        return;
    int mid = st[id].mid();
    build(L(id),l,mid);
    build(R(id),mid,r);
}
void pushUp(int id)
{
    if(st[id].cnt > 0)
    {
        st[id].sum = dy[st[id].r] - dy[st[id].l];
        return ;
    }
    if(st[id].l + 1== st[id].r)
    {
        st[id].sum = 0;
        return ;
    }
    st[id].sum = st[L(id)].sum + st[R(id)].sum;
}
void update(int id,int l,int r,int fg)
{
    if(st[id].l >= l && st[id].r <= r)
    {
        st[id].cnt += fg;
        pushUp(id);
        return ;
    }
    int mid = st[id].mid();
    if(mid >= r)
        update(L(id),l,r,fg);
    else if(mid <= l)
        update(R(id),l,r,fg);
    else
    {
        update(L(id),l,mid,fg);
        update(R(id),mid,r,fg);
    }

    pushUp(id);

}
int main()
{
    int t,i,j,cas = 0;
    scanf("%d",&t);
    while(t--)
    {
        cnt = 0;
        scanf("%d%d",&n,&m);
        for(i = 1; i <= m; ++i)
            scanf("%d",pri + i);
        for(i = 0; i < n; ++i)
            cube[i].input();

        sort(pri,pri + m + 1);
        sort(dy,dy + cnt);
        cnt = unique(dy,dy + cnt) - dy;

        __int64 res = 0LL;

        for(i = 1; i <= m; ++i)
        {
            int tot = 0,l,r;
            __int64 area = 0LL;
            for(j = 0; j < n; ++j)
                if(cube[j].h >= pri[i])
                {
                    sg[tot++] = _seg(cube[j].x1,cube[j].y1,cube[j].y2,1);
                    sg[tot++] = _seg(cube[j].x2,cube[j].y1,cube[j].y2,-1);
                }
            sort(sg,sg + tot,cmp);
            build(1,0,cnt);
            for(j = 0; j < tot - 1; ++j)
            {
                l = lower_bound(dy,dy + cnt, sg[j].y1) - dy;
                r = lower_bound(dy,dy + cnt, sg[j].y2) - dy;
                update(1,l,r,sg[j].flag);
                area += 1LL * st[1].sum * (1LL * sg[j+1].x - 1LL * sg[j].x);
            }
            res += area * (1LL * pri[i] - 1LL * pri[i-1]);
        }
        printf("Case %d: %I64d\n",++cas,res);
    }
    return 0;
}