【问题描述】
发起进攻。
在二维母世界诞生的你,第一次见到了三维世界的恢弘壮阔。可惜你无暇过多欣赏,你接收到的命令是:斩草除根!
三维世界可以看成是一个 $A \times B \times C $ 的立方体,由于你的文明还没有完全掌握三维世界的结构,现在你还只有三种不够成熟的进攻路线:
1 a b: 将所有 $x \leq a, y \leq b $ 的世界毁灭。
2 a b: 将所有 $y\leq a, z \leq b $ 的世界毁灭。
3 a b: 将所有 $z \leq a, x \leq b $ 的世界毁灭。
最终你计划了 $n$ 次进攻,你想知道你摧毁了这个世界多少的体积。
【输入格式】
从文件c.in中读入数据。
第一行四个数 $n,A,B,C$。接下来 $n$ 行,每行三个数 $type, a, b $,表示一次进攻,其中 $type$ 表示进攻路线, $a,b$ 为进攻的参数。
【输出格式】
输出到文件c.out中。
一个数表示答案。
【样例输入输出】
2 4 4 4
2 2 3
3 2 2
32
通过容斥原理可以计算得出,$24+16-8=32$
【数据范围】
对于所有数据,有: $ n \leq 3 \times 10^5, 1\leq A,B,C \leq 10^6,u \leq A, v \leq B,w \leq C$
输入均为正整数。
子任务编号 | 特殊性质 | 分值 |
---|---|---|
1 | $n,A,B,C \leq 50$ | 20 |
2 | $C=1$ | 10 |
3 | $type=1$ | 10 |
4 | $type\leq2$ | 10 |
5 | 性质1 | 30 |
6 | 无 | 20 |
- 性质1: n 是 3 的倍数,且每三次切割可以分为一组,每组切割都遵循如下形式: $$ 1 \space u \space v \\ 2\space v \space w \\ 3\space w\space u \\ $$
其中,相同字母代表相同的数。