自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 22:51:05，当前版本为作者最后更新于2023-09-21 19:13:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里是官方题解。

众所周知，设长方体的长、宽、高分别为 $a,b,c$，则长方体的体积 $V=abc$。显然，经过若干次操作后，蛋糕的剩余部分依然是长方体。我们只需要知道每次操作后，剩余部分的长、宽、高分别是多少，即可解决问题。

考察剩余部分的横坐标 $x$，由于每次操作只会切掉 $x\le k$ 的部分，因此任意时刻剩余部分的 $x$ 一定是一段后缀 $x > k_{\max}$。这段后缀的长度是好求的，只需要维护当前所有对 $x$ 的切割的 $k$ 的最大值即可。纵坐标和竖坐标 $y,z$ 同理。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

int a, b, c, m, x, y, z;

int main() {
    for(scanf("%d%d%d%d", &a, &b, &c, &m); m; m--) {
        int op, k;
        scanf("%d%d", &op, &k);
        if(op == 1) chkmax(x, k);
        else if(op == 2) chkmax(y, k);
        else chkmax(z, k);
        printf("%lld\n", 1LL * (a - x) * (b - y) * (c - z));
    }
    return 0;
}