2021-05-08：给定两个非负数组x和hp，长度都是N，再给定一个正数range

package main

import "fmt"

func main() {

    if true {
        x := []int{0, 1, 2, 3, 4, 5, 6}
        hp := []int{6, 4, 2, 9, 3, 6, 4}
        range2 := 4
        ret := minAoe1(x, hp, range2)
        fmt.Println(ret)
    }

    if true {
        x := []int{0, 1, 2, 3, 4, 5, 6}
        hp := []int{6, 4, 2, 9, 3, 6, 4}
        range2 := 4
        ret := minAoe2(x, hp, range2)
        fmt.Println(ret)
    }

}

// 贪心策略：永远让最左边缘以最优的方式(AOE尽可能往右扩，最让最左边缘盖住目前怪的最左)变成0，也就是选择：
// 一定能覆盖到最左边缘, 但是尽量靠右的中心点
// 等到最左边缘变成0之后，再去找下一个最左边缘...
func minAoe1(x []int, hp []int, range2 int) int {
    N := len(x)
    ans := 0
    for i := 0; i < N; i++ {
        if hp[i] > 0 {
            triggerPost := i
            for triggerPost < N && x[triggerPost]-x[i] <= range2 {
                triggerPost++
            }
            ans += hp[i]
            aoe(x, hp, i, triggerPost-1, range2)
        }
    }
    return ans
}

func aoe(x []int, hp []int, L int, trigger int, range2 int) {
    N := len(x)
    RPost := trigger
    for RPost < N && x[RPost]-x[trigger] <= range2 {
        RPost++
    }
    minus := hp[L]
    for i := L; i < RPost; i++ {
        hp[i] = getMax(0, hp[i]-minus)
    }
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

// 贪心策略和方法二一样，但是需要用线段树，可优化成O(N * logN)的方法，
func minAoe2(x []int, hp []int, range2 int) int {
    N := len(x)
    // coverLeft[i]：如果以i为中心点放技能，左侧能影响到哪，下标从1开始，不从0开始
    // coverRight[i]：如果以i为中心点放技能，右侧能影响到哪，下标从1开始，不从0开始
    coverLeft := make([]int, N+1)
    coverRight := make([]int, N+1)
    left := 0
    right := 0
    for i := 0; i < N; i++ {
        for x[i]-x[left] > range2 {
            left++
        }
        for right < N && x[right]-x[i] <= range2 {
            right++
        }
        coverLeft[i+1] = left + 1
        coverRight[i+1] = right
    }
    // best[i]: 如果i是最左边缘点，选哪个点做技能中心点最好，下标从1开始，不从0开始
    best := make([]int, N+1)
    trigger := 0
    for i := 0; i < N; i++ {
        for trigger < N && x[trigger]-x[i] <= range2 {
            trigger++
        }
        best[i+1] = trigger
    }
    st := NewSegmentTree(hp)
    st.build(1, N, 1)
    ans := 0
    for i := 1; i <= N; i++ {
        leftEdge := st.query(i, i, 1, N, 1)
        if leftEdge > 0 {
            ans += leftEdge
            t := best[i]
            l := coverLeft[t]
            r := coverRight[t]
            st.add(l, r, (int)(-leftEdge), 1, N, 1)
        }
    }
    return ans
}

type SegmentTree struct {

    // arr[]为原序列的信息从0开始，但在arr里是从1开始的
    // sum[]模拟线段树维护区间和
    // lazy[]为累加懒惰标记
    // change[]为更新的值
    // update[]为更新慵懒标记
    MAXN    int
    arr     []int
    sum     []int
    lazy    []int
    change2 []int
    update2 []bool
}

func NewSegmentTree(origin []int) *SegmentTree {
    ret := &SegmentTree{}
    MAXN := len(origin) + 1
    ret.arr = make([]int, MAXN) // arr[0] 不用 从1开始使用
    for i := 1; i < MAXN; i++ {
        ret.arr[i] = origin[i-1]
    }
    ret.sum = make([]int, MAXN<<2)      // 用来支持脑补概念中，某一个范围的累加和信息
    ret.lazy = make([]int, MAXN<<2)     // 用来支持脑补概念中，某一个范围沒有往下傳遞的纍加任務
    ret.change2 = make([]int, MAXN<<2)  // 用来支持脑补概念中，某一个范围有没有更新操作的任务
    ret.update2 = make([]bool, MAXN<<2) // 用来支持脑补概念中，某一个范围更新任务，更新成了什么
    return ret
}

func (this *SegmentTree) pushUp(rt int) {
    this.sum[rt] = this.sum[rt<<1] + this.sum[rt<<1|1]
}

// 之前的，所有懒增加，和懒更新，从父范围，发给左右两个子范围
// 分发策略是什么
// ln表示左子树元素结点个数，rn表示右子树结点个数
func (this *SegmentTree) pushDown(rt int, ln int, rn int) {
    if this.update2[rt] {
        this.update2[rt<<1] = true
        this.update2[rt<<1|1] = true
        this.change2[rt<<1] = this.change2[rt]
        this.change2[rt<<1|1] = this.change2[rt]
        this.lazy[rt<<1] = 0
        this.lazy[rt<<1|1] = 0
        this.sum[rt<<1] = this.change2[rt] * ln
        this.sum[(rt<<1)|1] = this.change2[rt] * rn
        this.update2[rt] = false
    }
    if this.lazy[rt] != 0 {
        this.lazy[rt<<1] += this.lazy[rt]
        this.sum[rt<<1] += this.lazy[rt] * ln
        this.lazy[(rt<<1)|1] += this.lazy[rt]
        this.sum[(rt<<1)|1] += this.lazy[rt] * rn
        this.lazy[rt] = 0
    }
}

// 在初始化阶段，先把sum数组，填好
// 在arr[l~r]范围上，去build，1~N，
// rt : 这个范围在sum中的下标
func (this *SegmentTree) build(l int, r int, rt int) {
    if l == r {
        this.sum[rt] = this.arr[l]
        return
    }
    mid := (l + r) >> 1
    this.build(l, mid, rt<<1)
    this.build(mid+1, r, rt<<1|1)
    this.pushUp(rt)
}

func (this *SegmentTree) update(L int, R int, C int, l int, r int, rt int) {
    if L <= l && r <= R {
        this.update2[rt] = true
        this.change2[rt] = C
        this.sum[rt] = C * (r - l + 1)
        this.lazy[rt] = 0
        return
    }
    // 当前任务躲不掉，无法懒更新，要往下发
    mid := (l + r) >> 1
    this.pushDown(rt, mid-l+1, r-mid)
    if L <= mid {
        this.update(L, R, C, l, mid, rt<<1)
    }
    if R > mid {
        this.update(L, R, C, mid+1, r, rt<<1|1)
    }
    this.pushUp(rt)
}

// L..R -> 任务范围 ,所有的值累加上C
// l,r -> 表达的范围
// rt 去哪找l，r范围上的信息
func (this *SegmentTree) add(L int, R int, C int, l int, r int, rt int) {
    // 任务的范围彻底覆盖了，当前表达的范围
    if L <= l && r <= R {
        this.sum[rt] += C * (r - l + 1)
        this.lazy[rt] += C
        return
    }
    // 任务并没有把l...r全包住
    // 要把当前任务往下发
    // 任务 L, R 没有把本身表达范围 l,r 彻底包住
    mid := (l + r) >> 1 // l..mid (rt << 1) mid+1...r(rt << 1 | 1)
    // 下发之前所有攒的懒任务
    this.pushDown(rt, mid-l+1, r-mid)
    // 左孩子是否需要接到任务
    if L <= mid {
        this.add(L, R, C, l, mid, rt<<1)
    }
    // 右孩子是否需要接到任务
    if R > mid {
        this.add(L, R, C, mid+1, r, rt<<1|1)
    }
    // 左右孩子做完任务后，我更新我的sum信息
    this.pushUp(rt)
}

// 1~6 累加和是多少？ 1~8 rt
func (this *SegmentTree) query(L int, R int, l int, r int, rt int) int {
    if L <= l && r <= R {
        return this.sum[rt]
    }
    mid := (l + r) >> 1
    this.pushDown(rt, mid-l+1, r-mid)
    ans := 0
    if L <= mid {
        ans += this.query(L, R, l, mid, rt<<1)
    }
    if R > mid {
        ans += this.query(L, R, mid+1, r, rt<<1|1)
    }
    return ans
}