Total Submission(s): 3758 Accepted Submission(s): 1203
Problem Description
Jack knows that there is a great underground treasury in a secret region. And he has a special device that can be used to detect treasury under the surface of the earth. One day he got outside with the device to ascertain the treasury. He chose many different locations on the surface of the earth near the secret region. And at each spot he used the device to detect treasury and got some data from it representing a region, which may contain treasury below the surface. The data from the device at each spot is six integers x1, y1, z1, x2, y2 and z2 (x1<x2, y1<y2, z1<z2). According to the instruction of the device they represent the range of x, y and z coordinates of the region. That is to say, the x coordinate of the region, which may contain treasury, ranges from x1 to x2. So do y and z coordinates. The origin of the coordinates is a fixed point under the ground.
Jack can’t get the total volume of the treasury because these regions don’t always contain treasury. Through years of experience, he discovers that if a region is detected that may have treasury at more than two different spots, the region really exist treasure. And now Jack only wants to know the minimum volume of the treasury.
Now Jack entrusts the problem to you.
Input
The first line of the input file contains a single integer t, the number of test cases, followed by the input data for each test case.
Each test case is given in some lines. In the first line there is an integer n (1 ≤ n ≤ 1000), the number of spots on the surface of the earth that he had detected. Then n lines follow, every line contains six integers x1, y1, z1, x2, y2 and z2, separated by a space. The absolute value of x and y coordinates of the vertices is no more than 106, and that of z coordinate is no more than 500.
Output
For each test case, you should output “Case a: b” in a single line. a is the case number, and b is the minimum volume of treasury. The case number is counted from one.
Sample Input
2
1
0 0 0 5 6 4
3
0 0 0 5 5 5
3 3 3 9 10 11
3 3 3 13 20 45
Sample Output
Case 1: 0
Case 2: 8
因为之前没有搞博客，所以注释都写在代码里了，我这个人也比较懒，就不提取出来了，稍微改一下好了。。。
代码
先放一份自己的弱鸡pushdown代码（C++ TLE。。。）感觉就修改覆盖几次方便，不用像只有pushup的版本一样写一大堆tree。。。
AC 4633ms G++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145/*
emmm这是一道三维求重叠至少3次的体积...
应该要离散化。。。
思路1（太麻烦）：我感觉先算重叠的x-y轴面积，然后再乘重叠z轴。。。
思路2(错。。难实现)：每一面都算一遍重叠面积，然后乘起来就是xy*xz*yz=x2*y2*z2,开根号就是体积xyz了。。。
百度思路：暴力枚举z轴，反正就500。。。
然后就超时啦。。。
memset搞小也没用。。。
只能离散z轴再枚举了
*/
using namespace std;
const int maxn=2000;
const int fuck=1e6;//原谅我的粗暴
int tree[maxn<<2|3];
int flag[maxn<<2|3];//记录标记
int x[maxn<<2|3];//离散x轴并记录下来
int ak[maxn<<2|3];//离散z轴并记录下来
struct Node
{
int l,r,h;
int cov;
}line[maxn<<2|3];//存每条边的左端点l，右端点r，和y轴坐标h，以及cov存的是上边还是下边，下边为1，上边为-1，从下往上扫描
struct sNode
{
int x,y,z;
}sx[maxn<<2|3];//记录题目提供的数据，因为下面在遍历每个z坐标时需要从题目给的数据中提取出在z坐标范围内符合的数据
bool cmp(Node a,Node b)
{
return a.h<b.h;
}
void pushup(int rt)
{
tree[rt]=tree[rt<<1]+tree[rt<<1|1];//这里不用担心会pushup错，因为比如父树不混乱且已经覆盖了三层，然后需要updata他的左子树，因为有pushdown，所以右子树也是有值的，所以是可以保证一个标记不混乱的父树的所有子树都有值且有标记，所以即使不管怎么updata，pushup上来都是对的。所以这种如果查询区间，可以保证每个区间都是正确的，而下面那种updata版本就不行
if (flag[rt<<1]!=flag[rt<<1|1]) flag[rt]=-1;//如果左子树和右子树标记不一样，父树标记就记为-1，代表标记混乱，找的时候就要去找子树了
else flag[rt]=flag[rt<<1];
}
void pushdown(int l,int r,int m,int rt)
{
if (flag[rt]!=-1)//如果标记不混乱就下推标记
{
flag[rt<<1]=flag[rt<<1|1]=flag[rt];
if (flag[rt]<=2)/*！！！此处和其他2处可以通过修改<=的值来达到任意求覆盖多少层的效果！！！*/
{
tree[rt<<1]=tree[rt<<1|1]=0;
}
else
{
tree[rt<<1]=x[m]-x[l-1];//因为下面主函数里是l+1，r进来的，所以这里l-1
tree[rt<<1|1]=x[r]-x[m];
}
}
}
void updata(int nl,int nr,int nc,int l,int r,int rt)
{
if (nl<=l&&r<=nr&&flag[rt]!=-1)//标记不混乱才可以进去更新。当然，不用担心当l==r时，因为l==r时标记肯定不混乱，因为l==r已经没有子树给他混乱了
{
flag[rt]+=nc;//加上标记，可以算出来覆盖了几层，flag肯定大于等于0
if (flag[rt]<=2)/*！！！此处和其他2处可以通过修改<=的值来达到任意求覆盖多少层的效果！！！*/
{
tree[rt]=0;
}
else
{
tree[rt]=x[r]-x[l-1];
}
return;
}
int m=(l+r)>>1;
pushdown(l,r,m,rt);
if (nl<=m) updata(nl,nr,nc,l,m,rt<<1);
if (nr>m) updata(nl,nr,nc,m+1,r,rt<<1|1);
pushup(rt);
}
int main()
{
int n,t,cnt,real_cnt,cas=0,cont,real_cont;
int x1,y1,z1,x2,y2,z2;
//int minn_z=501;
//int maxn_z=-501;
long long ans;
scanf("%d",&t);
while (t--)
{
ans=0;
cont=0;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
x1+=fuck;
y1+=fuck;
x2+=fuck;
y2+=fuck;//把负坐标变正
ak[++cont]=z1;
ak[++cont]=z2;//离散z轴
sx[i].x=x1;
sx[i].y=y1;
sx[i].z=z1;
sx[i+n].x=x2;
sx[i+n].y=y2;
sx[i+n].z=z2;//存数据
}
sort(ak+1,ak+cont+1);
real_cont=unique(ak+1,ak+cont+1)-ak-1;//去重
for (int k=1;k<real_cont;k++)//枚举z轴，相当于切黄瓜一样，一层一层算，而且z都是整数,这里用k防止和sx的z混淆
{
cnt=0;
for (int i=1;i<=n;i++)
{
if (sx[i].z<=ak[k]&&ak[k]<sx[i+n].z)//右边只取到<号，为了排除像这种1 1 1 2 2 2 / 1 1 1 8 8 8 错算成2的情况，和下面扫描线只到倒数第二根一个道理
{
x[++cnt]=sx[i].x;
line[cnt].l=sx[i].x;
line[cnt].r=sx[i+n].x;
line[cnt].h=sx[i].y;
line[cnt].cov=1;
x[++cnt]=sx[i+n].x;
line[cnt].l=sx[i].x;
line[cnt].r=sx[i+n].x;
line[cnt].h=sx[i+n].y;
line[cnt].cov=-1;//符合数据的进来
}
}//下面语句附带剪枝效果
if (cnt<=2) continue;/*！！！此处和其他2处可以通过修改<=的值来达到任意求覆盖多少层的效果！！！*/
sort(x+1,x+cnt+1);
real_cnt=unique(x+1,x+cnt+1)-x-1;
sort(line+1,line+cnt+1,cmp);
memset(flag,0,(cnt<<2|3)*sizeof(flag[0]));
memset(tree,0,(cnt<<2|3)*sizeof(tree[0]));
for (int i=1;i<cnt;i++)
{
int l=lower_bound(x+1,x+real_cnt+1,line[i].l)-x;
int r=lower_bound(x+1,x+real_cnt+1,line[i].r)-x;
updata(l+1,r,line[i].cov,1,real_cnt,1);
ans+=1ll*tree[1]*(line[i+1].h-line[i].h)*(ak[k+1]-ak[k]);//乘上这个，因为如果z轴是一个是2一个是4，那3肯定是连续体积的，2~4不会是不连续的
}
}
printf("Case %d: %lld\n",++cas,ans);
}
}
第二份只有pushup版的代码。感谢wxk博客帮助我理解下面wxk天下第一，推一波wxk的博客MingSD
AC 1045ms G++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143/*
加个这个(l==r)?0:感觉保险一点，防止rt<<1和rt<<1|1溢出。。。
*/
using namespace std;
const int maxn=2000;
const int fuck=1e6;
int tree[maxn<<2|3],tree2[maxn<<2|3],tree3[maxn<<2|3];//tree表示覆盖1次的（即没有覆盖的）、tree2表示覆盖2次的，tree3表示覆盖3次及以上的
int flag[maxn<<2|3];
int x[maxn<<2|3];
int ak[maxn<<2|3];
//int cz[fuck*2+3];
struct Node
{
int l,r,h;
int cov;
Node(){};
Node(int x1,int x2,int y,int c)
{
l=x1;
r=x2;
h=y;
cov=c;
}//写上这个就可以愉快地使用形如line[cnt]=Node(sx[i].x,sx[i+n].x,sx[i].y,1);这样的东西
}line[maxn<<2|3];
struct sNode
{
int x,y,z;
sNode(){};
sNode(int x1,int y1,int z1)
{
x=x1;
y=y1;
z=z1;
}
}sx[maxn<<2|3];
bool cmp(Node a,Node b)
{
return a.h<b.h;
}
void pushup(int l,int r,int rt)
{
if (flag[rt]>=3)//因为下面是r-1，所以这里都是r+1
{
tree3[rt]=x[r+1]-x[l];
tree[rt]=tree2[rt]=0;
}
else if (flag[rt]==2)
{
tree3[rt]=(l==r)?0:tree3[rt<<1]+tree3[rt<<1|1]+tree2[rt<<1]+tree2[rt<<1|1]+tree[rt<<1]+tree[rt<<1|1];//该区间flag为2，因为没有下推，所以左右子树可能会有flag=1、2、3的，然后加上该区间的flag的值2，肯定会大于等于3。。。
tree2[rt]=x[r+1]-x[l]-tree3[rt];
tree[rt]=0;
}
else if (flag[rt]==1)
{
tree3[rt]=(l==r)?0:tree3[rt<<1]+tree3[rt<<1|1]+tree2[rt<<1]+tree2[rt<<1|1];//同理只有子树flag=2、3，然后加上父亲的flag的值1才会大于等于3
tree2[rt]=(l==r)?0:tree[rt<<1]+tree[rt<<1|1];//同理子树flag=1加上父亲的flag的值1才会大于等于2
tree[rt]=x[r+1]-x[l]-tree3[rt]-tree2[rt];
}
else if (l==r) tree[rt]=tree2[rt]=tree3[rt]=0;//因为上三种情况都没有那肯定是当前没有覆盖，面积肯定是0呀，且没子树了，所以单独列出来
else
{
tree[rt]=tree[rt<<1]+tree[rt<<1|1];
tree2[rt]=tree2[rt<<1]+tree2[rt<<1|1];
tree3[rt]=tree3[rt<<1]+tree3[rt<<1|1];
}
}
void updata(int nl,int nr,int nc,int l,int r,int rt)
{
if (nl<=l&&r<=nr)
{
flag[rt]+=nc;
pushup(l,r,rt);//注意这里要写这个，比较特殊。因为子树可能可以通过父树的标记加上自己子树的标记满足题目条件
return;
}
int m=(l+r)>>1;
if (nl<=m) updata(nl,nr,nc,l,m,rt<<1);
if (nr>m) updata(nl,nr,nc,m+1,r,rt<<1|1);
pushup(l,r,rt);//不用担心有节点离父树好几层，无法加到，导致少加了一些。因为每次pushup上来可以保证某一层以上的都是正确的，然后如果需要updata更深层的，虽然最深层到那某一层的路途中可能都是错误的，但是可以保证的是，继续向上pushup上来，某一层包括自己及以上的都是正确的，所以往最坏的情况想至少可以保证tree[1],tree2[1],tree3[1]是正确的。
}
int main()
{
int n,t,cnt,real_cnt,cas=0,cont,real_cont;
int x1,y1,z1,x2,y2,z2;
long long ans;
scanf("%d",&t);
while (t--)
{
ans=0;
cont=0;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d%d%d%d%d%d",&sx[i].x,&sx[i].y,&sx[i].z,&sx[i+n].x,&sx[i+n].y,&sx[i+n].z);
sx[i].x+=fuck;
sx[i].y+=fuck;
sx[i+n].x+=fuck;
sx[i+n].y+=fuck;
ak[++cont]=sx[i].z;
ak[++cont]=sx[i+n].z;//离散z轴
}
sort(ak+1,ak+cont+1);
real_cont=unique(ak+1,ak+cont+1)-ak-1;
for (int k=1;k<real_cont;k++)//枚举z轴，相当于切黄瓜一样，一层一层算，而且z都是整数,这里用k防止和sx的z混淆
{
cnt=0;
for (int i=1;i<=n;i++)
{
if (sx[i].z<=ak[k]&&ak[k]<sx[i+n].z)//排除像这种1 1 1 2 2 2 / 1 1 1 8 8 8 错算成2的情况
{
x[++cnt]=sx[i].x;
line[cnt]=Node(sx[i].x,sx[i+n].x,sx[i].y,1);
x[++cnt]=sx[i+n].x;
line[cnt]=Node(sx[i].x,sx[i+n].x,sx[i+n].y,-1);
}
}
if (cnt<=2) continue;//剪枝并且控制重叠次数语句
sort(x+1,x+cnt+1);
real_cnt=unique(x+1,x+cnt+1)-x-1;
sort(line+1,line+cnt+1,cmp);
/*for (int i=1;i<=real_cnt;i++)
{
cz[x[i]]=i;
}*/
for (int i=(cnt<<2|3);i>=1;i--)
{
flag[i]=tree[i]=tree2[i]=tree3[i]=0;
}
for (int i=1;i<cnt;i++)
{
int l=lower_bound(x+1,x+real_cnt+1,line[i].l)-x;
int r=lower_bound(x+1,x+real_cnt+1,line[i].r)-x;
updata(l,r-1,line[i].cov,1,real_cnt,1);//下面的-1是为了弥补比如原来(3,3)的空档，注意-1位置，和我之前的习惯不一样，虽然也可以用我那种。。。
ans+=1ll*tree3[1]*(line[i+1].h-line[i].h)*(ak[k+1]-ak[k]);//乘上这个，因为如果z轴是一个是2一个是4，那3肯定是连续体积的，2~4不会是不连续的
}
}
printf("Case %d: %lld\n",++cas,ans);
}
}
两种版本时间区别这么大的原因（仅代表个人观点）：第一种因为保证了每个区间都是正确的，可能updata时前半部分的区间范围条件已经满足，但总是标记混乱，直到最后l==r时，这就导致了效率极其低下，因为此题不需要每个区间都正确，只需要下标为1的第一个区间即可。然后第二种就是只保证了下标为1的区间的正确性，不保证下面的正确与否，updata一到满足的区间就立马updata了，效率就快很多了。。。