結果
| 問題 |
No.1099 Range Square Sum
|
| コンテスト | |
| ユーザー |
 草苺奶昔
|
| 提出日時 | 2023-04-01 17:45:14 |
| 言語 | Go (1.23.4) |
| 結果 |
AC
|
| 実行時間 | 349 ms / 2,000 ms |
| コード長 | 6,047 bytes |
| コンパイル時間 | 13,735 ms |
| コンパイル使用メモリ | 225,032 KB |
| 実行使用メモリ | 26,424 KB |
| 最終ジャッジ日時 | 2024-09-24 11:09:13 |
| 合計ジャッジ時間 | 17,531 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 30 |
ソースコード
package main
import (
"bufio"
"fmt"
"math/bits"
"os"
)
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int
fmt.Fscan(in, &n)
nums := make([]int, n)
for i := 0; i < n; i++ {
fmt.Fscan(in, &nums[i])
}
leaves := make([]E, n)
for i := 0; i < n; i++ {
leaves[i] = E{1, nums[i], nums[i] * nums[i]}
}
tree := NewLazySegTree(leaves)
var q int
fmt.Fscan(in, &q)
for i := 0; i < q; i++ {
var op int
fmt.Fscan(in, &op)
if op == 1 {
var l, r, v int
fmt.Fscan(in, &l, &r, &v)
l--
tree.Update(l, r, v)
} else {
var l, r int
fmt.Fscan(in, &l, &r)
l--
res := tree.Query(l, r)
fmt.Fprintln(out, res.sum2)
}
}
}
const INF = 1e18
// RangeAddRangeSquareSum
type E = struct{ sum0, sum1, sum2 int } // !0次和(size),1次和(sum),2次和(square sum)
type Id = int
func (*LazySegTree) e() E { return E{} }
func (*LazySegTree) id() Id { return 0 }
func (*LazySegTree) op(left, right E) E {
return E{left.sum0 + right.sum0, left.sum1 + right.sum1, left.sum2 + right.sum2}
}
func (*LazySegTree) mapping(f Id, g E) E {
return E{g.sum0, g.sum1 + f*g.sum0, g.sum2 + 2*g.sum1*f + g.sum0*f*f}
}
func (*LazySegTree) composition(f, g Id) Id {
return f + g
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a < b {
return b
}
return a
}
// !template
type LazySegTree struct {
n int
size int
log int
data []E
lazy []Id
}
func NewLazySegTree(leaves []E) *LazySegTree {
tree := &LazySegTree{}
n := len(leaves)
tree.n = n
tree.log = int(bits.Len(uint(n - 1)))
tree.size = 1 << tree.log
tree.data = make([]E, tree.size<<1)
tree.lazy = make([]Id, tree.size)
for i := range tree.data {
tree.data[i] = tree.e()
}
for i := range tree.lazy {
tree.lazy[i] = tree.id()
}
for i := 0; i < n; i++ {
tree.data[tree.size+i] = leaves[i]
}
for i := tree.size - 1; i >= 1; i-- {
tree.pushUp(i)
}
return tree
}
// 查询切片[left:right]的值
// 0<=left<=right<=len(tree.data)
func (tree *LazySegTree) Query(left, right int) E {
if left < 0 {
left = 0
}
if right > tree.n {
right = tree.n
}
if left >= right {
return tree.e()
}
left += tree.size
right += tree.size
for i := tree.log; i >= 1; i-- {
if ((left >> i) << i) != left {
tree.pushDown(left >> i)
}
if ((right >> i) << i) != right {
tree.pushDown((right - 1) >> i)
}
}
sml, smr := tree.e(), tree.e()
for left < right {
if left&1 != 0 {
sml = tree.op(sml, tree.data[left])
left++
}
if right&1 != 0 {
right--
smr = tree.op(tree.data[right], smr)
}
left >>= 1
right >>= 1
}
return tree.op(sml, smr)
}
func (tree *LazySegTree) QueryAll() E {
return tree.data[1]
}
// 更新切片[left:right]的值
// 0<=left<=right<=len(tree.data)
func (tree *LazySegTree) Update(left, right int, f Id) {
if left < 0 {
left = 0
}
if right > tree.n {
right = tree.n
}
if left >= right {
return
}
left += tree.size
right += tree.size
for i := tree.log; i >= 1; i-- {
if ((left >> i) << i) != left {
tree.pushDown(left >> i)
}
if ((right >> i) << i) != right {
tree.pushDown((right - 1) >> i)
}
}
l2, r2 := left, right
for left < right {
if left&1 != 0 {
tree.propagate(left, f)
left++
}
if right&1 != 0 {
right--
tree.propagate(right, f)
}
left >>= 1
right >>= 1
}
left = l2
right = r2
for i := 1; i <= tree.log; i++ {
if ((left >> i) << i) != left {
tree.pushUp(left >> i)
}
if ((right >> i) << i) != right {
tree.pushUp((right - 1) >> i)
}
}
}
// 二分查询最小的 left 使得切片 [left:right] 内的值满足 predicate
func (tree *LazySegTree) MinLeft(right int, predicate func(data E) bool) int {
if right == 0 {
return 0
}
right += tree.size
for i := tree.log; i >= 1; i-- {
tree.pushDown((right - 1) >> i)
}
res := tree.e()
for {
right--
for right > 1 && right&1 != 0 {
right >>= 1
}
if !predicate(tree.op(tree.data[right], res)) {
for right < tree.size {
tree.pushDown(right)
right = right<<1 | 1
if predicate(tree.op(tree.data[right], res)) {
res = tree.op(tree.data[right], res)
right--
}
}
return right + 1 - tree.size
}
res = tree.op(tree.data[right], res)
if (right & -right) == right {
break
}
}
return 0
}
// 二分查询最大的 right 使得切片 [left:right] 内的值满足 predicate
func (tree *LazySegTree) MaxRight(left int, predicate func(data E) bool) int {
if left == tree.n {
return tree.n
}
left += tree.size
for i := tree.log; i >= 1; i-- {
tree.pushDown(left >> i)
}
res := tree.e()
for {
for left&1 == 0 {
left >>= 1
}
if !predicate(tree.op(res, tree.data[left])) {
for left < tree.size {
tree.pushDown(left)
left <<= 1
if predicate(tree.op(res, tree.data[left])) {
res = tree.op(res, tree.data[left])
left++
}
}
return left - tree.size
}
res = tree.op(res, tree.data[left])
left++
if (left & -left) == left {
break
}
}
return tree.n
}
// 单点查询(不需要 pushUp/op 操作时使用)
func (tree *LazySegTree) Get(index int) E {
index += tree.size
for i := tree.log; i >= 1; i-- {
tree.pushDown(index >> i)
}
return tree.data[index]
}
// 单点赋值
func (tree *LazySegTree) Set(index int, e E) {
index += tree.size
for i := tree.log; i >= 1; i-- {
tree.pushDown(index >> i)
}
tree.data[index] = e
for i := 1; i <= tree.log; i++ {
tree.pushUp(index >> i)
}
}
func (tree *LazySegTree) pushUp(root int) {
tree.data[root] = tree.op(tree.data[root<<1], tree.data[root<<1|1])
}
func (tree *LazySegTree) pushDown(root int) {
if tree.lazy[root] != tree.id() {
tree.propagate(root<<1, tree.lazy[root])
tree.propagate(root<<1|1, tree.lazy[root])
tree.lazy[root] = tree.id()
}
}
func (tree *LazySegTree) propagate(root int, f Id) {
tree.data[root] = tree.mapping(f, tree.data[root])
// !叶子结点不需要更新lazy
if root < tree.size {
tree.lazy[root] = tree.composition(f, tree.lazy[root])
}
}