吉老师线段树模板题 HDU5306 Gorgeous Sequence
维护一个序列 aaa: 0 l r t ∀l≤i≤r,ai=min(ai,t)\forall l\le i\le r,a_i=min(a_i,t)∀l≤i≤r,ai=min(ai,t)。 1 l r 输出区间 [l,r][l,r][l,r] 中的最大值。 2 l r 输出区间和。 多组数据,T≤100,n≤106,∑m≤106T\le 100,n\le 10^6,\sum m\le 10^6T≤100,n≤106,∑m≤106
维护一个序列 aaa:
0 l r t ∀l≤i≤r,ai=min(ai,t)\forall l\le i\le r,a_i=min(a_i,t)∀l≤i≤r,ai=min(ai,t)。
0 l r t
1 l r 输出区间 [l,r][l,r][l,r] 中的最大值。
1 l r
2 l r 输出区间和。
2 l r
多组数据,T≤100,n≤106,∑m≤106T\le 100,n\le 10^6,\sum m\le 10^6T≤100,n≤106,∑m≤106
OIWiki 的 std 中 pushdown 函数中只更新了 mx、sum 和 tag 的值,这样怎么保证正确性呢?
pushdown
mx
sum
tag