ICPC2019 西安邀请赛 H. Minecraft
题目链接
https://nanti.jisuanke.com/t/39275
题目大意
一个 $N \times M \times H$ 的 $Minecraft$ 世界，每次操作将一个对角为 $(x_1, y_1, z_1)$ 和 $(x_2, y_2, z_2)$ 的长方体区域全部变为石头，问每次询问后石头区域的联通块数量和非石头区域的联通块数量。
题目分析
题目一眼看过去感觉像是三维线段树，但是感觉空间不太够而且题目给的数据范围的上限好像可以让我乱胡，所以决定写了个分块的思路。
首先考虑石头区域的联通块数量，显然非常好处理，对于每次的长方体进行求交并查集一下就可以了。难点在于，如果处理非石头的区域。显然这是一道倒着做的套路题。
那么也就是说需要求出来每次操作后增加的点都是那些。考虑使用分块来解决这个问题，将整个空间分成 $\sqrt{N} \times \sqrt{M} \times \sqrt{H}$ 块，那么显然经过一定的操作之后，在某一块中的所有点都将变为石头。这样可以优化掉大量的复杂度。
其实线段树的做法应该也是这个思路，复杂度也是这个原理，但是不如分块好写。而且在我的电脑上分块的代码专门构造的极限数据跑了 $3.7s$ ，在题目要求的 $4s$ 范围之内，而且有了题目的数据范围的限制之后仅跑了 $168ms$ 。随机数据跑的也飞快。
所以，分块还是极好的！
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e6 + 5;
const int maxm = 105;
int n, m, h, q, t;
int fa[maxn];
bool s[maxm][maxm][maxm];
int dx[] = {1, -1, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};
int ans = 0;
pair <int, int> anss[1005];
bool f[1005][1005];
struct block {
short int a, b, c;
short int x, y, z;
int cnt;
} bk[1005];
int bcnt = 0;
struct point {
short int x, y, z;
};
vector <point> opt[1005];
struct ex {
short int a, b, c;
short int x, y, z;
};
ex que[1005];
int read(){
int x;
scanf("%d", &x);
return x;
}
bool val(int x, int y, int z){
if(0 <= x and x < n and 0 <= y and y < m and 0 <= z and z < h){
return true;
}
return false;
}
int getn(int x, int y, int z){
return x * (m * h) + y * h + z + 1;
}
int find(int x){
if(fa[x] != x){
fa[x] = find(fa[x]);
}
return fa[x];
}
int join(int x, int y){
int ra = find(x);
int rb = find(y);
if(ra != rb){
ans--;
fa[ra] = rb;
}
return 0;
}
int build(){
int i, j, k, l, r, p;
int ba = sqrt(n) + 0.5, bb = sqrt(m) + 0.5, bc = sqrt(h) + 0.5;
for(i=0;i<n;i+=ba){
for(j=0;j<m;j+=bb){
for(k=0;k<h;k+=bc){
bcnt++;
bk[bcnt] = {i, j, k, min(n, i + ba) - 1, min(m, j + bb) - 1, min(h, k + bc) - 1, 0};
bk[bcnt].cnt = 1 * (bk[bcnt].x - bk[bcnt].a + 1) * (bk[bcnt].y - bk[bcnt].b + 1) * (bk[bcnt].z - bk[bcnt].c + 1);
}
}
}
for(l=1;l<=q;l++){
for(r=1;r<=bcnt;r++){
if(bk[r].cnt == 0)continue;
for(i=max(que[l].a, bk[r].a);i<=min(que[l].x, bk[r].x);i++){
for(j=max(que[l].b, bk[r].b);j<=min(que[l].y, bk[r].y);j++){
for(k=max(que[l].c, bk[r].c);k<=min(que[l].z, bk[r].z);k++){
if(!s[i][j][k]){
s[i][j][k] = true;
opt[l].push_back({i, j, k});
bk[r].cnt--;
}
}
}
}
}
}
return 0;
}
int solve(){
int i, j, k, l, r, p;
int a, b, c;
int x, y, z;
for(l=1;l<=q;l++){
for(r=l+1;r<=q;r++){
if(max(que[l].a, que[r].a) <= min(que[l].x, que[r].x)){
if(max(que[l].b, que[r].b) <= min(que[l].y, que[r].y)){
if(max(que[l].c, que[r].c) <= min(que[l].z, que[r].z)){
f[l][r] = f[r][l] = true;
}
}
}
if(max(que[l].a, que[r].a) <= min(que[l].x, que[r].x) + 1){
if(max(que[l].b, que[r].b) <= min(que[l].y, que[r].y)){
if(max(que[l].c, que[r].c) <= min(que[l].z, que[r].z)){
f[l][r] = f[r][l] = true;
}
}
}
if(max(que[l].a, que[r].a) <= min(que[l].x, que[r].x)){
if(max(que[l].b, que[r].b) <= min(que[l].y, que[r].y) + 1){
if(max(que[l].c, que[r].c) <= min(que[l].z, que[r].z)){
f[l][r] = f[r][l] = true;
}
}
}
if(max(que[l].a, que[r].a) <= min(que[l].x, que[r].x)){
if(max(que[l].b, que[r].b) <= min(que[l].y, que[r].y)){
if(max(que[l].c, que[r].c) <= min(que[l].z, que[r].z) + 1){
f[l][r] = f[r][l] = true;
}
}
}
}
}
for(i=1;i<=q;i++){
ans++;
for(j=1;j<=i-1;j++){
if(f[i][j]){
join(i, j);
}
}
anss[i].first = ans;
}
/*----------*/
build();
for(i=1;i<=n*m*h;i++){
fa[i] = i;
}
ans = 0;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
for(k=0;k<h;k++){
if(s[i][j][k])continue;
ans++;
for(p=0;p<6;p++){
if(val(i + dx[p], j + dy[p], k + dz[p]) and !s[i + dx[p]][j + dy[p]][k + dz[p]]){
join(getn(i, j, k), getn(i + dx[p], j + dy[p], k + dz[p]));
}
}
}
}
}
anss[q].second = ans;
for(l=q;l>1;l--){
for(point tmp : opt[l]){
i = tmp.x;
j = tmp.y;
k = tmp.z;
ans++;
s[i][j][k] = false;
for(p=0;p<6;p++){
if(val(i + dx[p], j + dy[p], k + dz[p]) and !s[i + dx[p]][j + dy[p]][k + dz[p]]){
join(getn(i, j, k), getn(i + dx[p], j + dy[p], k + dz[p]));
}
}
}
anss[l - 1].second = ans;
}
return 0;
}
int main(){
int i, j;
int a, b, c;
int x, y, z;
t = read();
while(t--){
memset(s, 0, sizeof(s));
memset(f, 0, sizeof(f));
for(i=0;i<=1000;i++)opt[i].clear();
ans = 0;
bcnt = 0;
n = read();
m = read();
h = read();
q = read();
for(i=1;i<=q;i++){
fa[i] = i;
}
for(i=1;i<=q;i++){
a = read();
b = read();
c = read();
x = read();
y = read();
z = read();
que[i] = {a, b, c, x, y, z};
}
solve();
for(i=1;i<=q;i++){
printf("%d %d\n", anss[i].first, anss[i].second);
}
}
return 0;
}