Link

题意

分析

区间修改模板。

代码

package main

import (
    "bufio"
    . "fmt"
    "os"
)

type seg []struct {
    l, r      int
    todo, sum int64 // 给以当前节点为根的子树中的每一个节点加上todo这个数(不包含当前节点)
}

func do(t seg, o int, add int64) {
    t[o].todo += add
    t[o].sum += int64(t[o].r-t[o].l+1) * add // % mod
}

func pushUp(t seg, o int) {
    t[o].sum = t[o<<1].sum + t[o<<1|1].sum
}

func pushDown(t seg, o int) {
    if add := t[o].todo; add != 0 {
        do(t, o<<1, add)
        do(t, o<<1|1, add)
        t[o].todo = 0
    }
}

func build(t seg, a []int64, o, l, r int) {
    t[o].l, t[o].r = l, r
    if l == r {
        t[o].sum = a[l-1]
        return
    }
    m := (l + r) >> 1
    build(t, a, o<<1, l, m)
    build(t, a, o<<1|1, m+1, r)
    pushUp(t, o)
}

func update(t seg, o, l, r int, add int64) {
    if l <= t[o].l && t[o].r <= r {
        do(t, o, add)
        return
    }
    pushDown(t, o)
    m := (t[o].l + t[o].r) >> 1
    if l <= m {
        update(t, o<<1, l, r, add)
    }
    if m < r {
        update(t, o<<1|1, l, r, add)
    }
    pushUp(t, o)
}

func query(t seg, o, l, r int) int64 {
    if l <= t[o].l && t[o].r <= r {
        return t[o].sum
    }
    pushDown(t, o)
    m := (t[o].l + t[o].r) >> 1
    if r <= m {
        return query(t, o<<1, l, r)
    }
    if l > m {
        return query(t, o<<1|1, l, r)
    }
    return query(t, o<<1, l, r) + query(t, o<<1|1, l, r)
}

func main() {
    r, w := bufio.NewReader(os.Stdin), bufio.NewWriter(os.Stdout)
    defer w.Flush()

    var n, m, op, x, y int
    Fscan(r, &n, &m)
    a := make([]int64, n)
    for i := range a {
        Fscan(r, &a[i])
    }
    t := make(seg, 4*len(a))
    build(t, a, 1, 1, len(a))
    for i := 0; i < m; i++ {
        var k int64
        Fscan(r, &op)
        if op == 1 {
            Fscan(r, &x, &y, &k)
            update(t, 1, x, y, k)
        } else {
            Fscan(r, &x, &y)
            Fprintln(w, query(t, 1, x, y))
        }
    }
}

动态开点版:

package main

import (
    "bufio"
    . "fmt"
    "os"
)

type LazyNode struct {
    lc, rc    *LazyNode
    l, r      int
    todo, sum int64
}

func (t *LazyNode) do(add int64) {
    t.todo += add
    t.sum += int64(t.r-t.l+1) * add
}

func (t *LazyNode) pushUp() {
    t.sum = t.lc.sum + t.rc.sum
}

func (t *LazyNode) pushDown() {
    m := (t.l + t.r) >> 1
    if t.lc == nil {
        t.lc = &LazyNode{l: t.l, r: m}
    }
    if t.rc == nil {
        t.rc = &LazyNode{l: m + 1, r: t.r}
    }
    if add := t.todo; add != 0 {
        t.lc.do(add)
        t.rc.do(add)
        t.todo = 0
    }
}

func (t *LazyNode) build(a []int64, l, r int) {
    t.l, t.r = l, r
    if l == r {
        t.sum = a[l-1]
        return
    }
    m := (l + r) >> 1
    t.lc = &LazyNode{}
    t.lc.build(a, l, m)
    t.rc = &LazyNode{}
    t.rc.build(a, m+1, r)
    t.pushUp()
}

func (t *LazyNode) update(l, r int, add int64) {
    if l <= t.l && t.r <= r {
        t.do(add)
        return
    }
    t.pushDown()
    m := (t.l + t.r) >> 1
    if l <= m {
        t.lc.update(l, r, add)
    }
    if m < r {
        t.rc.update(l, r, add)
    }
    t.pushUp()
}

func (t *LazyNode) query(l, r int) int64 {
    // 对于不在线段树中的点，应按照题意来返回
    if t == nil || l > t.r || r < t.l {
        return 0 // inf
    }
    if l <= t.l && t.r <= r {
        return t.sum
    }
    t.pushDown()
    m := (t.l + t.r) >> 1
    if r <= m {
        return t.lc.query(l, r)
    }
    if l > m {
        return t.rc.query(l, r)
    }
    return t.lc.query(l, r) + t.rc.query(l, r)
}

/**
链接: https://www.luogu.com.cn/problem/P3372
*/
func main() {
    r, w := bufio.NewReader(os.Stdin), bufio.NewWriter(os.Stdout)
    defer w.Flush()

    var n, m, op, x, y int
    Fscan(r, &n, &m)
    a := make([]int64, n)
    for i := range a {
        Fscan(r, &a[i])
    }
    t := &LazyNode{}
    t.build(a, 1, n)
    for i := 0; i < m; i++ {
        Fscan(r, &op)
        if op == 1 {
            var k int64
            Fscan(r, &x, &y, &k)
            t.update(x, y, k)
        } else {
            Fscan(r, &x, &y)
            Fprintln(w, t.query(x, y))
        }
    }
}