题意

有一棵 节点的树,根为 号节点。每个节点有两个权值 ,初始值均为

给出三种操作:

  1. 到根的路径上所有点的
  2. 到根的路径上所有点的
  3. 询问点 的权值

思路

如果单纯看的话需要维护的标记比较复杂,但是可以考虑使用矩阵乘法来描述。使用线段树维护矩阵和。对于操作 1,

对于操作 2

正确性可以得到保证(矩阵乘法满足结合律和对加法的分配律)

然后用线段树维护就很简单了。注意懒标记清空是清成单位矩阵。

最后修改日期:2021年1月14日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。