hdu 3642 Get The Treasury (线段树+扫描线，求长方体体积交)
题意：给出若干个（1000）长方体，求至少交三次的空间的体积。
尺寸为[x1,x2],[y1,y2],[z1,z2],其中x，y的坐标的绝对值不超过1E6,Z的坐标的绝对值不超过1E9.
思路：
线段树+扫描线。
由于Z的坐标范围比较小，我们的做法是 利用“微分”的思想，将每个长方体，想成若干的高度为1的矩形（矩形片）
因此就转化成了求矩形至少交三次的面积
其中和矩形交，也就是矩形至少交2次的面积比较类似，只不过线段树多维护一个至少三次覆盖的长度的域。
1void PushUp(int l,int r,int rt)
2{
3 //cout<<"l:"<<l<<" r:"<<r<<" rt:"<<rt<<" id:"<<id<<endl;
4 if (tree[rt].cnt>=3)
5 {
6 tree[rt].one = tree[rt].two = tree[rt].three = X[r+1]-X[l];
7 }
8 else
9 if (tree[rt].cnt==2)
10 {
11 tree[rt].one = tree[rt].two = X[r+1]-X[l];
if (l==r) tree[rt].three = 0 ;
else tree[rt].three = tree[rt<<1].one + tree[rt<<1|1].one;
1 }else if (tree[rt].cnt==1)
2 {
3 tree[rt].one = X[r+1] - X[l];
1 if (l==r) tree[rt].two = tree[rt].three = 0;
2 else
3 {
4 tree[rt].two = tree[rt<<1].one + tree[rt<<1|1].one;
5 tree[rt].three = tree[rt<<1].two + tree[rt<<1|1].two;
6 }
7 }
8 else
9 {
10 if (l==r) tree[rt].one = tree[rt].two = tree[rt].three = 0;
11 else
12 {
13 tree[rt].one = tree[rt<<1].one + tree[rt<<1|1].one;
14 tree[rt].two = tree[rt<<1].two + tree[rt<<1|1].two;
15 tree[rt].three = tree[rt<<1].three + tree[rt<<1|1].three;
16 }
17 }
18}
假设我们有一个长为5，宽为6，高为7的长方体
那么我们就要将其拆成7个，长为5，宽为6的矩形
将所有长方体处理完之后，枚举高度，对于每一个高度，如果矩形大于等于三个，就做一个“矩形的三次面积交”操作，将答案累加。
2A，PushUp的时候写错了一句。。。即如果父亲节点已经覆盖了两次，那么父亲节点被覆盖三次的是从左右儿子被覆盖一次的情况得来的
/* ***********************************************
Author :111qqz
Created Time :2017年09月28日 星期四 14时18分35秒
File Name :hdu3642.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E3+7;
7int n;
8struct Seg
9{
10 LL l,r,h;
11 int d;
12 Seg(){}
13 Seg(LL l,LL r,LL h,int d):l(l),r(r),h(h),d(d){}
14 bool operator < (const Seg & rhs)const
15 {
16 return h < rhs.h;
17 }
18}a[N];
19struct Tree
20{
21 LL one,two,three;
22 int cnt;
23}tree[N<<2];
24LL X[N],Z[N];
25struct Cube
26{
27 LL x1,y1,z1,x2,y2,z2;
28}cube[N];
29struct Rec
30{
31 LL x1,y1,x2,y2;
32 void print()
33 {
34 printf("x1:%lld y1:%lld x2:%lld y2:%lld\n",x1,y1,x2,y2);
35 }
36 Rec(){}
37 Rec(LL x1, LL y1,LL x2, LL y2):x1(x1),y1(y1),x2(x2),y2(y2){}
38};
39vector< Rec >rec[N];
40void PushUp(int l,int r,int rt)
41{
42 //cout<<"l:"<<l<<" r:"<<r<<" rt:"<<rt<<" id:"<<id<<endl;
43 if (tree[rt].cnt>=3)
44 {
45 tree[rt].one = tree[rt].two = tree[rt].three = X[r+1]-X[l];
46 }
47 else
48 if (tree[rt].cnt==2)
49 {
50 tree[rt].one = tree[rt].two = X[r+1]-X[l];
if (l==r) tree[rt].three = 0 ;
else tree[rt].three = tree[rt<<1].one + tree[rt<<1|1].one;
1 }else if (tree[rt].cnt==1)
2 {
3 tree[rt].one = X[r+1] - X[l];
1 if (l==r) tree[rt].two = tree[rt].three = 0;
2 else
3 {
4 tree[rt].two = tree[rt<<1].one + tree[rt<<1|1].one;
5 tree[rt].three = tree[rt<<1].two + tree[rt<<1|1].two;
6 }
7 }
8 else
9 {
10 if (l==r) tree[rt].one = tree[rt].two = tree[rt].three = 0;
11 else
12 {
13 tree[rt].one = tree[rt<<1].one + tree[rt<<1|1].one;
14 tree[rt].two = tree[rt<<1].two + tree[rt<<1|1].two;
15 tree[rt].three = tree[rt<<1].three + tree[rt<<1|1].three;
16 }
17 }
18}
19void update( int L,int R,int val,int l,int r,int rt)
20{
21 if (L<=l && r<=R)
22 {
23 tree[rt].cnt +=val;
24 PushUp(l,r,rt);
25 return;
26 }
27 int m = (l+r)>>1;
28 if (L<=m) update(L,R,val,lson);
29 if (R>=m+1) update(L,R,val,rson);
30 PushUp(l,r,rt);
31}
1LL solve( int z)
2{
3 int siz = rec[z].size();
4 if (siz<3) return 0LL;
5 // for ( int i = 0 ; i < siz ; i++) rec[z][i].print();
6 ms(tree,0);
7 for ( int i = 0 ; i < siz ; i++)
8 {
9 LL x1 = rec[z][i].x1;
10 LL y1 = rec[z][i].y1;
11 LL x2 = rec[z][i].x2;
12 LL y2 = rec[z][i].y2;
13// printf("x1:%lld y1:%lld x2:%lld y2:%lld\n",x1,y1,x2,y2);
14 X[i+1] = x1;
15 X[i+1+siz] = x2;
16 a[i+1]=Seg(x1,x2,y1,1);
17 a[i+1+siz]=Seg(x1,x2,y2,-1);
18 }
19 siz<<=1;
20 sort(X+1,X+siz+1);
21 sort(a+1,a+siz+1);
22 int m = unique(X+1,X+siz+1)-X-1;
23 LL ret = 0;
24 for ( int i = 1 ; i < siz; i++)
25 {
26 int l = lower_bound(X+1,X+m+1,a[i].l)-X;
27 int r = lower_bound(X+1,X+m+1,a[i].r)-X;
28 update(l,r-1,a[i].d,1,m,1);
29 ret += tree[1].three * (a[i+1].h-a[i].h);
30 }
31 //cout<<"Z:"<<z<<" ret:"<<ret<<endl;
32 return ret;
33}
34int main()
35{
36 #ifndef ONLINE_JUDGE
37 freopen("./in.txt","r",stdin);
38 #endif
39 int T;
40 int cas = 0;
41 cin>>T;
42 while (T--)
43 {
44 scanf("%d",&n);
45 ms(tree,0);
46 for ( int i = 0 ; i < N ; i++) rec[i].clear();
47 for ( int i = 1 ; i <= n ; i++)
48 {
49 scanf("%lld %lld %lld",&cube[i].x1,&cube[i].y1,&cube[i].z1);
50 scanf("%lld %lld %lld",&cube[i].x2,&cube[i].y2,&cube[i].z2);
51 //此处先存储下来是为了将Z坐标离散化
52 Z[i] = cube[i].z1;
53 Z[i+n] = cube[i].z2;
54 for ( int j = cube[i].z1 ; j < cube[i].z2 ; j++)
55 {
56 rec[j+500].PB(Rec(cube[i].x1,cube[i].y1,cube[i].x2,cube[i].y2));
57 }
58 }
59 LL ans = 0;
60 for ( int i = 0 ; i <=1000 ; i++)
61 {
62 ans += solve(i);
63 }
64 printf("Case %d: %lld\n",++cas,ans);
65 }
66 #ifndef ONLINE_JUDGE
67 fclose(stdin);
68 #endif
69 return 0;
70}