arr数组长度为n, magic数组长度为m
比如 arr = { 3, 1, 4, 5, 7 },如果完全不改变arr中的值,
那么收益就是累加和 = 3 + 1 + 4 + 5 + 7 = 20
magics[i] = {a,b,c} 表示arr[a~b]中的任何一个值都能改成c
并且每一种操作,都可以执行任意次,其中 0 <= a <= b < n
那么经过若干次的魔法操作,你当然可能得到arr的更大的累加和
返回arr尽可能大的累加和
n <= 10^7 m <= 10^6 arr中的值和c的范围 <= 10^12
线段树。
代码用golang编写。代码如下:
package main
import (
"fmt"
"sort"
)
func main() {
arr := []int{3, 1, 4, 5, 7}
magics := [][]int{{2, 5, 5}, {1, 3, 2}}
ret := maxSum3(arr, magics)
fmt.Println(ret)
}
// O(N) + O(M * logM) + O(M * logN) + O(N)
func maxSum3(arr []int, magics [][]int) int {
n := len(arr)
st := NewSegmentTree3(n)
sort.Slice(magics, func(i, j int) bool {
a := magics[i]
b := magics[j]
return a[2] < b[2]
})
for _, magic := range magics {
st.update0(magic[0]+1, magic[1]+1, magic[2], 1, n, 1)
}
ans := 0
query := st.buildSingleQuery(n)
for i := 0; i < n; i++ {
ans += getMax(query[i], arr[i])
}
return ans
}
// 为方法三特别定制的线段树
// 区间上维持最大值的线段树
// 支持区间值更新
// 为本道题定制了一个方法:
// 假设全是单点查询,请统一返回所有单点的结果(一个结果数组,里面有所有单点记录)
type SegmentTree3 struct {
max []int
change []int
update []bool
index int
}
func NewSegmentTree3(size int) *SegmentTree3 {
ans := &SegmentTree3{}
N := size + 1
ans.max = make([]int, N<<2)
ans.change = make([]int, N<<2)
ans.update = make([]bool, N<<2)
return ans
}
func (this *SegmentTree3) pushUp(rt int) {
this.max[rt] = getMax(this.max[rt<<1], this.max[rt<<1|1])
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func (this *SegmentTree3) pushDown(rt, ln, rn int) {
if this.update[rt] {
this.update[rt<<1] = true
this.update[rt<<1|1] = true
this.change[rt<<1] = this.change[rt]
this.change[rt<<1|1] = this.change[rt]
this.max[rt<<1] = this.change[rt]
this.max[rt<<1|1] = this.change[rt]
this.update[rt] = false
}
}
func (this *SegmentTree3) update0(L, R, C, l, r, rt int) {
if L <= l && r <= R {
this.update[rt] = true
this.change[rt] = C
this.max[rt] = C
return
}
mid := (l + r) >> 1
this.pushDown(rt, mid-l+1, r-mid)
if L <= mid {
this.update0(L, R, C, l, mid, rt<<1)
}
if R > mid {
this.update0(L, R, C, mid+1, r, rt<<1|1)
}
this.pushUp(rt)
}
func (this *SegmentTree3) buildSingleQuery(n int) []int {
ans := make([]int, n+1)
this.process(ans, 1, n, 1)
return ans
}
func (this *SegmentTree3) process(ans []int, l, r, rt int) {
if l == r {
ans[this.index] = this.max[rt]
this.index++
} else {
mid := (l + r) >> 1
this.pushDown(rt, mid-l+1, r-mid)
this.process(ans, l, mid, rt<<1)
this.process(ans, mid+1, r, rt<<1|1)
}
}
执行结果如下: