AC. 梦想

frank_c1

[HDU 5306] Gorgeous Sequence

发布于2016年06月03日 | 暂无评论 | 1,723阅读 | 线段树

题意简述

维护长度为n的序列a,有m组操作。

1.0 x y t:对于x \le i \le y,令a_i = \min(a_i,t)

2.1 x y:对于x \le i \le y,求a_i的最大值。

3.2 x y:对于x \le i \le y,求a_i的总和。

1 \le n,m \le 10 ^ 6, 1 \le x \le y \le n, 0 \le a_i,t \lt 2 ^ {31}

题目解析

小清新数据结构啊……

XYZ大爷和吉利爷太神啦!看了论文终于会做了,太神奇。

考虑线段树,我们发现这道题无法用经典的懒标记维护,怎么办呢?

我们对于线段树的每个结点,维护最大值max,最大值出现次数cnt,严格次大值sec和区间和sum

修改时,对于可修改结点x,若

1.t \ge max(x):修改对于该区间无效,返回。

2.sec(x) \lt t \lt max(x)t只对max(x)发生影响,令max(x) = t并更新区间和,返回。

3.sec(x) \le t:无法简单地更新区间和了……

怎么办呢?遇到第三种情况,继续向下DFS直到有结点满足条件1,2

这个复杂度靠谱吗?一开始是我是怀疑的,看完论文后我真心膜膜膜~~(证明待填...)

另外我想知道,这题现场有人做出来吗……