#P18485. When Anton Saw This Task He Reacted With 😩
When Anton Saw This Task He Reacted With 😩
When Anton Saw This Task He Reacted With 😩
给定两个三维向量 和 ,它们的叉积定义为
$$v\times w=(v_yw_z-v_zw_y,\ v_zw_x-v_xw_z,\ v_xw_y-v_yw_x).$$叉积长度为 ,其中 是两个向量的夹角;叉积方向同时垂直于 和 。整数坐标向量的叉积仍有整数坐标。
叉积不满足结合律,也就是说 不一定等于 。因此,若要支持修改一些向量并计算整个表达式的叉积,必须指定括号的位置。本题通过一棵树指定括号,无需解析表达式。
给定一棵 个点的有根树,点编号为 ,根是点 。每个点属于以下两类之一:
- 内部点:恰好有两个孩子,分别为左孩子 、右孩子 。
- 叶子:没有孩子,并写有一个向量 。
定义点 的值 :若为叶子,就是其写有的向量;若为内部点,则
$$\operatorname{val}(v)=\operatorname{val}(l)\times\operatorname{val}(r).$$有 次操作。每次给定一个叶子 和一个向量 ,将该叶子写有的向量替换为 ,然后输出根的值 。
所有答案坐标均对 取模。若某次操作后真实根向量为 ,可以输出任何分别与这三个数模 同余、且各自处于 signed32 范围的整数。
输入格式
第一行两个整数 (,)。
随后 行,第 行描述点 :
- 若为内部点,该行形式为
x l r,其中 。首个字符是小写字母x,后面两个数依次为左、右孩子编号。 - 若为叶子,该行形式为
v x y z,其中 。首个字符是小写字母v,随后是该叶子上的向量。
保证这些行构成一棵以 为根的树。没有父节点编号小于孩子编号的额外保证。
随后 行,每行四个整数 v x y z,表示一次替换操作。其中 ,;保证 是叶子。
输出格式
每次操作后输出一行三个整数 ,分别与真实根向量的三个坐标模 同余,并且都满足
负数同余表示也合法。应当恰好输出 个三元组。
原样例
输入:
5 3
x 2 3
v 1 0 1
x 4 5
v 0 2 1
v 1 1 1
4 1 2 3
5 0 1 1
4 0 2 2
输出:
998244351 0 2
1 -2 998244352
0 0 0
样例说明
以下四张原图依次表示初始状态、第一次操作后、第二次操作后和第三次操作后:




第一次操作后,根的值为 。
第二次操作后,根的值为 。
依照题意,输出 -2 和 998244351 都可以表示 。