luogu#P9713. 「QFOI R1」抱抱

    ID: 13682 Type: RemoteJudge 1000ms 512MiB Tried: 3 Accepted: 3 Difficulty: 2 Uploaded By: Tags>洛谷原创O2优化洛谷月赛

「QFOI R1」抱抱

题目描述

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

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

共进行 mm 次切蛋糕操作,每次按如下三种方式之一切分:

  1. 切出 xkx\le k 的部分分给大家。
  2. 切出 yky\le k 的部分分给大家。
  3. 切出 zkz\le k 的部分分给大家。

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

输入格式

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

接下来 mm 行,每行两个整数 op,kop,k,表示进行【题目描述】中的第 opop 种操作,参数为 kk

输出格式

mm 行,每行一个整数,表示剩余部分体积。

3 3 3 2
1 2
2 1
9
6
1000000 1000000 1000000 6
1 123456
2 654321
3 233333
2 111111
1 333333
3 1000000
876544000000000000
303002853376000000
232302288589217792
232302288589217792
176680542935560631
0

提示

样例 11 解释

第一次切蛋糕,将所有 x2x\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)$ 共 99 个。

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


样例 22 解释

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

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


数据范围

本题共 2020 个测试点,每个测试点 55 分。

对于全部数据,保证 1a,b,c1061\le a,b,c\le 10^61m2×1051\le m\le 2\times 10^5op{1,2,3}op\in\{1,2,3\},若 op=1op=11ka1\le k\le a,若 op=2op=21kb1\le k\le b,若 op=3op=31kc1\le k\le c

  • 对于测试点 151\sim 5:保证 a,b,c,m100a,b,c,m\le 100
  • 对于测试点 6106\sim 10:保证 b=c=1b=c=1op=1op=1
  • 对于测试点 111511\sim 15:保证 c=1c=1op{1,2}op\in\{1,2\}
  • 对于测试点 162016\sim 20:无特殊限制。