Farmer John's Cheese Block

题目描述

农夫 John 有一块立方体形状的奶酪，放置在三维坐标系中，范围从 $(0,0,0)$ 延伸到 $(N, N, N)$（$2 \leq N \leq 1000$）。农夫 John 将对这块奶酪进行一系列 $Q$ 次（$1 \leq Q \leq 2 \cdot 10^5$）更新操作。 对于每次更新操作，FJ 会挖去一块 $1$ × $1$ × $1$ 的奶酪小块，该小块从整数坐标 $(x, y, z)$ 延伸到 $(x+1, y+1, z+1)$，其中 $0\le x,y,z<N$。保证在 FJ 挖去的位置确实存在一块 $1$ × $1$ × $1$ 的奶酪。由于 FJ 在玩 Moocraft，即使挖去了下方的奶酪，重力也不会导致上方的奶酪掉落。 每次更新后，请输出 FJ 可以将一块 $1$ × $1$ × $N$ 的长方体砖块放入奶酪块中的不同放置方式数，使得砖块的任何部分都不与剩余的奶酪重叠。砖块的每个顶点都必须在三个坐标轴上具有位于 $[0,N]$ 范围内的整数坐标。FJ 可以任意旋转砖块。

输入格式

第一行包含 $N$ 和 $Q$。 接下来的 $Q$ 行每行包含 $x$、$y$ 和 $z$，表示要被挖去的位置坐标。

输出格式

每次更新操作后，输出一个整数，表示不同放置方式的数量。

2 5
0 0 0
1 1 1
0 1 0
1 0 0
1 1 0

0
0
1
2
5

提示

在前三次更新之后，跨越 $[0, 1]\times [0, 2]\times [0, 1]$ 的 $1\times 2 \times 1$ 砖块不会与剩余的奶酪重叠，因此它会对答案产生贡献。 SCORING: 输入 2-4：$N\le 10$ 且 $Q \le 1000$ 输入 5-7： $N\le 100$ 且 $Q \le 1000$ 输入 8-16：无额外限制 题目作者：Chongtian Ma, Alex Liang

标签: USACO|2024|Bronze

来源

USACO|2024|Bronze