「QFOI R1」抱抱

GitHub跳转原题关系图返回列表

每维只记录已被切掉的最大坐标，剩余部分始终是长方体，体积等于三个剩余长度之积，单次操作 O(1)。

OJ: luogu

题目 ID: P9713

难度:普及-

标签:模拟枚举思维数学

创建: 2026-10-02 15:23

更新: 2026-10-03 11:51

形式化题目

有一个点集

S=\{(x,y,z)\mid 1\leqslant x\leqslant a,\ 1\leqslant y\leqslant b,\ 1\leqslant z\leqslant c\}

共进行 $m$ 次操作，第 $i$ 次操作给出 $(op_i,k_i)$ ，表示从 $S$ 中删去所有满足“第 $op_i$ 维坐标 $\leqslant k_i$ ”的点：

$op_i=1$ ：删去所有 $x\leqslant k_i$ 的点；
$op_i=2$ ：删去所有 $y\leqslant k_i$ 的点；
$op_i=3$ ：删去所有 $z\leqslant k_i$ 的点。

注意 $k_i$ 是最初建立坐标系时的绝对坐标，不随之前的删除而改变；已经被删掉的点不会再次参与判断。

求每次操作之后 $S$ 中剩余点的个数。

暴力解法

思路

最直接的写法就是题面的逐字翻译：把蛋糕真的“摆出来”，用一个三维数组（或者压成一维的 alive[]）标记每个单位立方体还在不在，初始全部为 $1$ ，同时用一个变量记住当前还剩多少块。

对每次操作 $(op,k)$ ，把三个维度全部枚举一遍。遇到一个还没被切掉的格子时，看它在第 $op$ 维上的坐标是否 $\leqslant k$ ；若是，就把它标记成“已切掉”，并让剩余块数减一。枚举完就输出剩余块数。

这个做法不需要任何观察，正确性是一眼可见的，适合作为理解题意和对拍的基线。它的代价是每次操作都要把整个长方体重新扫一遍，包括那些早就被切掉的格子。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-02 15:23
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 写法就是题面的逐字翻译：开一个三维的“还在不在”标记，每次操作把符合条件的方块一个个删掉，
// 每删掉一个就让剩余个数减一，然后输出剩余个数。
// 复杂度是 O(a * b * c * m)，只在对拍用的小数据上运行。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a, b, c;
int m;

// 把三维坐标压成一维下标，省内存也省事：idx = ((x-1)*b + (y-1))*c + (z-1)
vector<char> alive;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b >> c >> m;

    ll total = a * b * c;
    alive.assign((size_t)total, 1); // 1 表示这个单位立方体还在

    for (int t = 1; t <= m; ++t) {
        int op;
        ll k;
        cin >> op >> k;

        // 一次操作：把所有满足“第 op 维坐标 <= k”的方块切掉
        for (ll x = 1; x <= a; ++x) {
            for (ll y = 1; y <= b; ++y) {
                for (ll z = 1; z <= c; ++z) {
                    size_t idx = (size_t)(((x - 1) * b + (y - 1)) * c + (z - 1));
                    if (alive[idx] == 0) {
                        continue; // 已经被前面的操作切掉了
                    }
                    ll pos;
                    if (op == 1) {
                        pos = x;
                    } else if (op == 2) {
                        pos = y;
                    } else {
                        pos = z;
                    }
                    if (pos <= k) {
                        alive[idx] = 0;
                        total--;
                    }
                }
            }
        }
        cout << total << "\n";
    }

    return 0;
}

复杂度

设 $V=abc$ 为单位立方体的总数。每次操作要枚举全部 $V$ 个格子，共 $m$ 次操作。

时间复杂度和空间复杂度分别为

O(Vm)=O(abcm),\qquad O(V)=O(abc)

在 $a,b,c\leqslant 100,m\leqslant 100$ 的测试点 $1\sim 5$ 上， $abcm$ 约 $10^8$ ，勉强可跑；但当边长升到 $10^6$ 、 $m$ 升到 $2\times10^5$ 时，光是存下所有格子就需要 $10^{18}$ 个标记，这个做法完全不可行。

瓶颈

瓶颈就在于：我们把每一个单位立方体都当成了独立对象去管理。

而题面其实从头到尾没有要求我们回答“某个具体的点还在不在”，它只问剩余总数。为了回答这个总数，我们却付出了维护 $abc$ 个标记的代价。

另一个更重要的事实是：一次操作只沿着一个坐标轴、在一个坐标值上切。也就是说，每次操作删掉的都是一整层（或几层）方块，而不是零散的几块。这意味着剩余集合的形状非常特殊，值得重新描述一遍。

正解

思路

先只看一维，把问题简化。

在一维（ $b=c=1$ ）的情形下， $S=\{1,2,\dots,a\}$ 。一次 $op=1,k$ 的操作删掉 $\{1,\dots,k\}$ ，剩下的就是 $\{k+1,\dots,a\}$ ，剩余个数是 $a-k$ 。再做一次 $op=1,k'$ ：

若 $k'\geqslant k$ ，剩 $\{k'+1,\dots,a\}$ ，个数 $a-k'$ ；
若 $k'<k$ ，这些点早就没了，剩余不变，个数还是 $a-k$ 。

换句话说，一维时只需要记住历史上出现过的最大 $k$ ：设 cut = max(所有 k)，答案恒为 $a-\text{cut}$ 。

这个观察能直接推到三维，原因是三次坐标的删除互不干涉：

删掉 $x\leqslant k$ 的点之后，剩下的点仍然满足“ $y$ 和 $z$ 的分布完全没变”。

所以我们可以逐维独立地做上面那件事。记

$\text{cut}_1=\max\{k_i\mid op_i=1\}$ （没有 $op=1$ 时为 $0$ ），
$\text{cut}_2=\max\{k_i\mid op_i=2\}$ ，
$\text{cut}_3=\max\{k_i\mid op_i=3\}$ ，

那么某一时刻的剩余集合恰好是

S'=\{(x,y,z)\mid \text{cut}_1<x\leqslant a,\ \text{cut}_2<y\leqslant b,\ \text{cut}_3<z\leqslant c\}

这仍然是一个长方体，它的体积就是三个方向剩余长度的乘积：

|S'|=(a-\text{cut}_1)(b-\text{cut}_2)(c-\text{cut}_3)

于是每次操作只需要：读入 $(op,k)$ ，做一次 cut[op] = max(cut[op], k)，然后输出上面这个乘积。一次操作 $O(1)$ 。

用样例 $1$ （ $a=b=c=3$ ）验证一下：

操作	$\text{cut}_1$	$\text{cut}_2$	剩余集合	体积
初始	0	0	$1..3\times1..3\times1..3$	27
`1 2`	2	0	$x=3$ 的那一层	$1\times3\times3=9$
`2 1`	2	1	$x=3,\ y\in\{2,3\}$	$1\times2\times3=6$

和样例输出 $9,6$ 一致。再用样例 $2$ 的第 $4$ 次操作检查“无效刀”：第二次操作已经把 $\text{cut}_2$ 推到 $654321$ ，第 $4$ 次操作的 $k=111111<654321$ ，max 之后什么都不变，所以输出与第 $3$ 次完全相同——这正是样例 $2$ 解释里说的那种情况。

正确性：对操作次数归纳。初始 $\text{cut}=(0,0,0)$ ， $S'$ 就是全部点，成立。假设某时刻成立，接着做一次 $(1,k)$ ：删除后

S'_{\text{new}}=S'\cap\{x>k\}=\{x>\text{cut}_1,\ x>k,\ \text{cut}_2<y\leqslant b,\ \text{cut}_3<z\leqslant c\}

而 $\{x>\text{cut}_1\}\cap\{x>k\}=\{x>\max(\text{cut}_1,k)\}$ ，正好与更新 cut[1]=max(cut[1],k) 后的形式相同； $op=2,3$ 对称。归纳完成，所以每次输出的乘积都等于真实剩余体积。

实现注意： $a,b,c\leqslant10^6$ ，体积最大可达 $10^{18}$ ，超过了 int，必须用 long long；读入输出用 %lld。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-02 15:23
 */
// P9713 「QFOI R1」抱抱
// 关键结论：每一刀都只沿着一个坐标轴切，且切的位置是初始的绝对坐标。
// 于是我们不需要真的维护蛋糕，只要记住：
//   cut[1] = 所有 op=1 的 k 的最大值（切掉 x <= cut[1] 的全部方块）
//   cut[2] = 所有 op=2 的 k 的最大值
//   cut[3] = 所有 op=3 的 k 的最大值
// 剩下的方块恰好是 x > cut[1] 且 y > cut[2] 且 z > cut[3] 的那个小长方体，
// 体积 = (a - cut[1]) * (b - cut[2]) * (c - cut[3])。
// 每次操作只需要用 k 更新一次最大值，再输出体积。
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

ll a, b, c;
int m;

// cut[i] 表示第 i 个维度上“被切掉的部分”能到达的最大坐标，初始为 0
ll cut[4];

void read_data() {
    scanf("%lld %lld %lld %d", &a, &b, &c, &m);
    for (int i = 1; i <= m; ++i) {
        int op;
        ll k;
        scanf("%d %lld", &op, &k);
        // 切的位置只增不减：k 比历史最大值小就说明这一刀已经没有方块可切
        if (k > cut[op]) {
            cut[op] = k;
        }
        // 剩余体积 = 三个方向剩余长度的乘积，最多 1e18，必须用 long long
        ll ans = (a - cut[1]) * (b - cut[2]) * (c - cut[3]);
        printf("%lld\n", ans);
    }
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    read_data();

    return 0;
}

复杂度

每次操作只做一次比较赋值和一次乘法，时间 $O(1)$ ，总时间

O(m)

额外空间只有三个变量，即 $O(1)$ 。

总结

这道题的关键在于不要被“切蛋糕”这个说法带着走。

一旦意识到每次操作都是沿坐标轴切走一整层，剩余部分的形状就始终是一个长方体；而“ $k$ 是初始的绝对坐标、不随操作改变”这个题面特意强调的条件，正是让三个维度可以各自只保留历史最大值的原因。抓住这两点，三维模拟就退化成了三个变量加一次乘法。

P9713 「QFOI R1」抱抱

题目描述

小 R 是一个可爱的女孩子，她希望跟大家抱抱，顺便给大家分蛋糕吃。

蛋糕是一个大小为 $a\times b\times c$ 的长方体，其中每个单位正方体都被赋予了一个坐标 $(x,y,z)$ （ $1\le x\le a,1\le y\le b,1\le z\le c$ ）。

共进行 $m$ 次切蛋糕操作，每次按如下三种方式之一切分：

切出 $x\le k$ 的部分分给大家。
切出 $y\le k$ 的部分分给大家。
切出 $z\le k$ 的部分分给大家。

由于她自己也想吃蛋糕，她希望知道在每次切蛋糕后，还剩下多少体积没有分给大家。

输入格式

第一行四个整数 $a,b,c,m$ ，表示蛋糕的大小和切蛋糕次数。

接下来 $m$ 行，每行两个整数 $op,k$ ，表示进行【题目描述】中的第 $op$ 种操作，参数为 $k$ 。

输出格式

$m$ 行，每行一个整数，表示剩余部分体积。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
29
6

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
71000000 1000000 1000000 6
1 123456
2 654321
3 233333
2 111111
1 333333
3 1000000

输出 #2

text

1
2
3
4
5
6876544000000000000
303002853376000000
232302288589217792
232302288589217792
176680542935560631
0

说明/提示

样例 $1$ 解释

第一次切蛋糕，将所有 $x\le 2$ 的部分切掉，剩余的单位正方体有 $(3,1,1),(3,1,2),(3,1,3),(3,2,1),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3)$ 共 $9$ 个。

第二次切蛋糕，将所有 $y\le 1$ 的部分切掉，剩余的单位正方体有 $(3,2,1),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3)$ 共 $6$ 个。

样例 $2$ 解释

第四次切蛋糕没有任何作用，因为第二次切蛋糕时 $y\le 654321$ 的部分已经被切掉，此时已经不存在 $y\le 111111$ 的单位正方体。

注意每次操作中的参数 $k$ 是初始时决定的绝对坐标，不会随着操作的进行而改变。

数据范围

本题共 $20$ 个测试点，每个测试点 $5$ 分。

对于全部数据，保证 $1\le a,b,c\le 10^6$ ， $1\le m\le 2\times 10^5$ ， $op\in\{1,2,3\}$ ，若 $op=1$ 则 $1\le k\le a$ ，若 $op=2$ 则 $1\le k\le b$ ，若 $op=3$ 则 $1\le k\le c$ 。

对于测试点 $1\sim 5$ ：保证 $a,b,c,m\le 100$ 。
对于测试点 $6\sim 10$ ：保证 $b=c=1$ ， $op=1$ 。
对于测试点 $11\sim 15$ ：保证 $c=1$ ， $op\in\{1,2\}$ 。
对于测试点 $16\sim 20$ ：无特殊限制。

「QFOI R1」抱抱

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

代码

复杂度

总结