Link

题意

题解

代码

package main

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

var mod int64

type seg []struct {
    l, r              int
    toAdd, toMul, sum int64
}

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

// 其实就是 不能直接 t[o].sum = (t[o].sum + toAdd) * toMul, 而是需要 t[o].sum = t[o].sum * toMul + toAdd(但是这个toAdd需要在乘过之前增加的mul)
func spread(t seg, o int, toAdd, toMul int64) {
    // add已经乘过mul了
    t[o].sum = (t[o].sum*toMul%mod + (int64(t[o].r-t[o].l+1) * toAdd % mod)) % mod
    t[o].toMul = t[o].toMul * toMul % mod
    // 这里也记得 * mul再加
    t[o].toAdd = (t[o].toAdd*toMul%mod + toAdd) % mod
}

func pushDown(t seg, o int) {
    toAdd, toMul := t[o].toAdd, t[o].toMul
    spread(t, o<<1, toAdd, toMul)
    spread(t, o<<1|1, toAdd, toMul)
    t[o].toAdd = 0
    t[o].toMul = 1
}

func build(t seg, a []int64, o, l, r int) {
    t[o].l, t[o].r, t[o].toMul = l, r, 1 // 这里toMul记得初始化为1
    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, op int, add int64) {
    if l <= t[o].l && t[o].r <= r {
        // op == 1 mul, op == 2 add
        if op == 1 {
            // add要在这里乘上k,因为后面可能要加其他的数而那些数其实是不用乘k的
            t[o].toAdd = t[o].toAdd * add % mod
            t[o].toMul = t[o].toMul * add % mod
            t[o].sum = t[o].sum * add % mod // 区间sum * add
        } else {
            t[o].toAdd = (t[o].toAdd + add) % mod
            t[o].sum = (t[o].sum + int64(t[o].r-t[o].l+1)*add) % mod
        }
        return
    }
    pushDown(t, o)
    m := (t[o].l + t[o].r) >> 1
    if l <= m {
        update(t, o<<1, l, r, op, add)
    }
    if m < r {
        update(t, o<<1|1, l, r, op, 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)%mod + query(t, o<<1|1, l, r)%mod
}

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, &mod)
    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 || op == 2 {
            Fscan(r, &x, &y, &k)
            update(t, 1, x, y, op, k)
        } else {
            Fscan(r, &x, &y)
            Fprintln(w, query(t, 1, x, y)%mod)
        }
    }
}