題意是說給出n個正方體，要求求出重疊n次的子長方體體積。
這題開始理解錯題意了，以為要求重疊的體積，懶得寫線段樹，就直接矩形切割，最壞復(fù)雜度n
4，這題數(shù)據(jù)也水的可以，竟然讓我過了，后來想了下，正確的做法應(yīng)該是枚舉長方體的端點，求左下角的點和右上角的點，然后直接算體積。。。
貼個水過去的代碼吧。。
1 # include <cstdio>
2 using namespace std;
3 # include <vector>
4 # include <map>
5 # include <algorithm>
6 # include <iostream>
7 struct node
8 {
9 int x1,x2,y1,y2,z1,z2;
10 bool operator<(const node &pos) const
11 {
12 if(x1!=pos.x1) return x1<pos.x1;
13 else if(x2!=pos.x2) return x2<pos.x2;
14 else if(y1!=pos.y1) return y1<pos.y1;
15 else if(y2!=pos.y2) return y2<pos.y2;
16 else if(z1!=pos.z1) return z1<pos.z1;
17 else return z2<pos.z2;
18 }
19 node(int x1,int y1,int z1,int x2,int y2,int z2)
20 {
21 this->x1=x1;
22 this->y1=y1;
23 this->x2=x2;
24 this->y2=y2;
25 this->z1=z1;
26 this->z2=z2;
27 }
28 };
29 map<node,int> refer;
30 vector<int> x;
31 vector<int> y;
32 vector<int> z;
33 vector<node> data;
34 int main()
35 {
36
37
38 while(true)
39 {
40 int num,total=0;
41 refer.clear();
42 x.clear();
43 y.clear();
44 z.clear();
45 data.clear();
46 scanf("%d",&num);
47 if(!num) break;
48 while(num--)
49 {
50 int tx,ty,tz,len;
51 scanf("%d%d%d%d",&tx,&ty,&tz,&len);
52 data.push_back(node(tx,ty,tz,tx+len,ty+len,tz+len));
53 x.push_back(tx);x.push_back(tx+len);
54 y.push_back(ty);y.push_back(ty+len);
55 z.push_back(tz);z.push_back(tz+len);
56 }
57 sort(x.begin(),x.end());
58 vector<int>::iterator end=unique(x.begin(),x.end());
59 while(x.end()!=end)
60 x.pop_back();
61 sort(y.begin(),y.end());
62 end=unique(y.begin(),y.end());
63 while(y.end()!=end)
64 y.pop_back();
65 sort(z.begin(),z.end());
66 end=unique(z.begin(),z.end());
67 while(z.end()!=end)
68 z.pop_back();
69 for(int i=0;i<data.size();i++)
70 {
71 vector<int>::iterator zbegin=lower_bound(z.begin(),z.end(),data[i].z1),zend=lower_bound(z.begin(),z.end(),data[i].z2),
72 ybegin=lower_bound(y.begin(),y.end(),data[i].y1),yend=lower_bound(y.begin(),y.end(),data[i].y2),
73 xbegin=lower_bound(x.begin(),x.end(),data[i].x1),xend=lower_bound(x.begin(),x.end(),data[i].x2);
74 for(vector<int>::iterator zp=zbegin;zp!=zend;zp++)
75 for(vector<int>::iterator yp=ybegin;yp!=yend;yp++)
76 for(vector<int>::iterator xp=xbegin;xp!=xend;xp++)
77 {
78 node tmp(*xp,*yp,*zp,*(xp+1),*(yp+1),*(zp+1));
79 //printf("%d %d %d %d %d %d\n",tmp.x1,tmp.y1,tmp.z1,tmp.x2,tmp.y2,tmp.z2);
80
81 refer[tmp]++;
82 if(refer[tmp]==data.size())
83 total+=(tmp.x2-tmp.x1)*(tmp.y2-tmp.y1)*(tmp.z2-tmp.z1);
84
85 }
86
87 }
88 printf("%d\n",total);
89 }
90 return 0;
91 }
92