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];
12
13 if (l==r) tree[rt].three = 0 ;
14 else tree[rt].three = tree[rt<<1].one + tree[rt<<1|1].one;
15
16 }else if (tree[rt].cnt==1)
17 {
18 tree[rt].one = X[r+1] - X[l];
19
20 if (l==r) tree[rt].two = tree[rt].three = 0;
21 else
22 {
23 tree[rt].two = tree[rt<<1].one + tree[rt<<1|1].one;
24 tree[rt].three = tree[rt<<1].two + tree[rt<<1|1].two;
25 }
26 }
27 else
28 {
29 if (l==r) tree[rt].one = tree[rt].two = tree[rt].three = 0;
30 else
31 {
32 tree[rt].one = tree[rt<<1].one + tree[rt<<1|1].one;
33 tree[rt].two = tree[rt<<1].two + tree[rt<<1|1].two;
34 tree[rt].three = tree[rt<<1].three + tree[rt<<1|1].three;
35 }
36 }
37}
假设我们有一个长为5，宽为6，高为7的长方体
那么我们就要将其拆成7个，长为5，宽为6的矩形
将所有长方体处理完之后，枚举高度，对于每一个高度，如果矩形大于等于三个，就做一个“矩形的三次面积交”操作，将答案累加。
2A，PushUp的时候写错了一句。。。即如果父亲节点已经覆盖了两次，那么父亲节点被覆盖三次的是从左右儿子被覆盖一次的情况得来的
1/* ***********************************************
2Author :111qqz
3Created Time :2017年09月28日 星期四 14时18分35秒
4File Name :hdu3642.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=2E3+7;
35int n;
36struct Seg
37{
38 LL l,r,h;
39 int d;
40 Seg(){}
41 Seg(LL l,LL r,LL h,int d):l(l),r(r),h(h),d(d){}
42 bool operator < (const Seg & rhs)const
43 {
44 return h < rhs.h;
45 }
46}a[N];
47struct Tree
48{
49 LL one,two,three;
50 int cnt;
51}tree[N<<2];
52LL X[N],Z[N];
53struct Cube
54{
55 LL x1,y1,z1,x2,y2,z2;
56}cube[N];
57struct Rec
58{
59 LL x1,y1,x2,y2;
60 void print()
61 {
62 printf("x1:%lld y1:%lld x2:%lld y2:%lld\n",x1,y1,x2,y2);
63 }
64 Rec(){}
65 Rec(LL x1, LL y1,LL x2, LL y2):x1(x1),y1(y1),x2(x2),y2(y2){}
66};
67vector< Rec >rec[N];
68void PushUp(int l,int r,int rt)
69{
70 //cout<<"l:"<<l<<" r:"<<r<<" rt:"<<rt<<" id:"<<id<<endl;
71 if (tree[rt].cnt>=3)
72 {
73 tree[rt].one = tree[rt].two = tree[rt].three = X[r+1]-X[l];
74 }
75 else
76 if (tree[rt].cnt==2)
77 {
78 tree[rt].one = tree[rt].two = X[r+1]-X[l];
79
80 if (l==r) tree[rt].three = 0 ;
81 else tree[rt].three = tree[rt<<1].one + tree[rt<<1|1].one;
82
83 }else if (tree[rt].cnt==1)
84 {
85 tree[rt].one = X[r+1] - X[l];
86
87 if (l==r) tree[rt].two = tree[rt].three = 0;
88 else
89 {
90 tree[rt].two = tree[rt<<1].one + tree[rt<<1|1].one;
91 tree[rt].three = tree[rt<<1].two + tree[rt<<1|1].two;
92 }
93 }
94 else
95 {
96 if (l==r) tree[rt].one = tree[rt].two = tree[rt].three = 0;
97 else
98 {
99 tree[rt].one = tree[rt<<1].one + tree[rt<<1|1].one;
100 tree[rt].two = tree[rt<<1].two + tree[rt<<1|1].two;
101 tree[rt].three = tree[rt<<1].three + tree[rt<<1|1].three;
102 }
103 }
104}
105void update( int L,int R,int val,int l,int r,int rt)
106{
107 if (L<=l && r<=R)
108 {
109 tree[rt].cnt +=val;
110 PushUp(l,r,rt);
111 return;
112 }
113 int m = (l+r)>>1;
114 if (L<=m) update(L,R,val,lson);
115 if (R>=m+1) update(L,R,val,rson);
116 PushUp(l,r,rt);
117}
118
119LL solve( int z)
120{
121 int siz = rec[z].size();
122 if (siz<3) return 0LL;
123 // for ( int i = 0 ; i < siz ; i++) rec[z][i].print();
124 ms(tree,0);
125 for ( int i = 0 ; i < siz ; i++)
126 {
127 LL x1 = rec[z][i].x1;
128 LL y1 = rec[z][i].y1;
129 LL x2 = rec[z][i].x2;
130 LL y2 = rec[z][i].y2;
131// printf("x1:%lld y1:%lld x2:%lld y2:%lld\n",x1,y1,x2,y2);
132 X[i+1] = x1;
133 X[i+1+siz] = x2;
134 a[i+1]=Seg(x1,x2,y1,1);
135 a[i+1+siz]=Seg(x1,x2,y2,-1);
136 }
137 siz<<=1;
138 sort(X+1,X+siz+1);
139 sort(a+1,a+siz+1);
140 int m = unique(X+1,X+siz+1)-X-1;
141 LL ret = 0;
142 for ( int i = 1 ; i < siz; i++)
143 {
144 int l = lower_bound(X+1,X+m+1,a[i].l)-X;
145 int r = lower_bound(X+1,X+m+1,a[i].r)-X;
146 update(l,r-1,a[i].d,1,m,1);
147 ret += tree[1].three * (a[i+1].h-a[i].h);
148 }
149 //cout<<"Z:"<<z<<" ret:"<<ret<<endl;
150 return ret;
151}
152int main()
153{
154 #ifndef ONLINE_JUDGE
155 freopen("./in.txt","r",stdin);
156 #endif
157 int T;
158 int cas = 0;
159 cin>>T;
160 while (T--)
161 {
162 scanf("%d",&n);
163 ms(tree,0);
164 for ( int i = 0 ; i < N ; i++) rec[i].clear();
165 for ( int i = 1 ; i <= n ; i++)
166 {
167 scanf("%lld %lld %lld",&cube[i].x1,&cube[i].y1,&cube[i].z1);
168 scanf("%lld %lld %lld",&cube[i].x2,&cube[i].y2,&cube[i].z2);
169 //此处先存储下来是为了将Z坐标离散化
170 Z[i] = cube[i].z1;
171 Z[i+n] = cube[i].z2;
172 for ( int j = cube[i].z1 ; j < cube[i].z2 ; j++)
173 {
174 rec[j+500].PB(Rec(cube[i].x1,cube[i].y1,cube[i].x2,cube[i].y2));
175 }
176 }
177 LL ans = 0;
178 for ( int i = 0 ; i <=1000 ; i++)
179 {
180 ans += solve(i);
181 }
182 printf("Case %d: %lld\n",++cas,ans);
183 }
184 #ifndef ONLINE_JUDGE
185 fclose(stdin);
186 #endif
187 return 0;
188}