NanoApe's Blog

既是咸鱼又是辣鸡

【开学Sept】Problems

NanoApe posted @ 2015年8月29日 21:02 in 蒟蒻不比赛何来学费 , 334 阅读

完成度:

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]


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter