抱抱 官方题解

· · 题解

这里是官方题解。

众所周知，设长方体的长、宽、高分别为 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;
}