【开学Sept】Problems
NanoApe
posted @ 2015年8月29日 21:02
in 蒟蒻不比赛何来学费
, 446 阅读
完成度：
0/18
[BC #53 D]
[BC #53 E]
[Hiho #14 C]
[Hiho #14 D]
[Nod #5 A]
[Nod #5 B]
[Nod #5 C]
[Nod #5 D]（JSH师兄有在线的做法！）
话说你那题是这样的。。如果对于是一个数组而不是树。。更新线段。。你把两种操作变成用这么几个三元组表示(a, b1, b2)
对于第一种操作是(d, 0, 0)
对于第二种操作是(0, d, 0)
然后三元组与三元组的操作是(a, b1, b2) * (a', b1', b2') = (a+a', b1+b1', b2+b2'+b1'a)
然后t = t + b1*v + b2
在这种情况下化成这样这个三元组是不用每次更新到点的。所以就可以利用lazy思想做线段树了
然后至于树上你就做成树链剖分吧
[Nod #5 E]
[Nod #5 F]
[BC #56 D]
[BC #56 E]
[Nod #6 A]
[Nod #6 B]
[Nod #6 C]
[Nod #6 D]
[Nod #6 E]
[Nod #6 F]
评论 (0)
NanoApe
ENE>.<~
计数器
153093
分类
搜索
听听看？
最新留言
最新评论
链接
RSS
