UOJ#164 清华集训V

传送门

http://uoj.ac/problem/164

题解

orz了ljh2000的题解QAQ这种题窝这种低智商儿童怎么可能会那样巨的构造

首先题目给出的第一感觉就是,要用一棵线段树来维护,但是怎么能够做到减得时候要保持v非负呢

我们构造一个二元组(a,b),他的意义是一种新运算,即x+(a,b)=max(a+x,b)

于是第一个操作就等价于加上一个(x,-\infty)

第二个操作等价于加上一个(-x,0)

第三个操作等价于加上一个(-\infty,x)

那么查询由于是单点查询,考虑把根到该点的路径上的标记全部下放,然后对这个点直接查询即可。

到此,有两个问题。

1.标记怎么合并?

考虑x先经过(a,b)再经过(c,d)

那么就有max\left\{max\left\{x+a,b\right\}+c,d\right\}

我们要想办法把x弄出来,就有max\left\{x+a+c,b+c,d\right\}

(a+c,max\left\{b+c,d\right\})

2.怎么做到查询历史最大值?

对标记维护历史最大值即可,下传时优先下传历史最大值标记。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注