【LG】P3373 【模板】线段树 2 【线段树】【TB】
2021/12/7 23:19:46
本文主要是介绍【LG】P3373 【模板】线段树 2 【线段树】【TB】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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) } } }
这篇关于【LG】P3373 【模板】线段树 2 【线段树】【TB】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署