#848480 (Go) No.880 Yet Another Segment Tree Problem

提出ソース

結果

問題	No.880 Yet Another Segment Tree Problem
ユーザー	草苺奶昔
提出日時	2023-03-11 19:17:34
言語	Go (1.22.1)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	6,946 bytes
コンパイル時間	12,671 ms
コンパイル使用メモリ	225,656 KB
実行使用メモリ	26,952 KB
最終ジャッジ日時	2024-09-22 20:05:57
合計ジャッジ時間	37,802 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 26,952 KB
testcase_01	AC	5 ms 6,812 KB
testcase_02	AC	5 ms 6,820 KB
testcase_03	AC	4 ms 6,944 KB
testcase_04	AC	4 ms 6,944 KB
testcase_05	AC	4 ms 6,944 KB
testcase_06	AC	3 ms 6,944 KB
testcase_07	AC	4 ms 6,944 KB
testcase_08	AC	4 ms 6,940 KB
testcase_09	AC	5 ms 6,944 KB
testcase_10	AC	4 ms 6,944 KB
testcase_11	AC	1,030 ms 24,436 KB
testcase_12	AC	987 ms 24,428 KB
testcase_13	AC	719 ms 22,336 KB
testcase_14	AC	981 ms 24,412 KB
testcase_15	AC	1,037 ms 24,412 KB
testcase_16	AC	1,091 ms 24,416 KB
testcase_17	AC	1,154 ms 24,408 KB
testcase_18	AC	1,147 ms 24,408 KB
testcase_19	AC	531 ms 24,412 KB
testcase_20	AC	538 ms 24,412 KB
testcase_21	AC	548 ms 24,420 KB
testcase_22	AC	531 ms 24,416 KB
testcase_23	AC	555 ms 24,412 KB
testcase_24	AC	486 ms 24,416 KB
testcase_25	AC	501 ms 24,412 KB
testcase_26	AC	525 ms 24,408 KB
testcase_27	AC	487 ms 24,416 KB
testcase_28	AC	518 ms 24,412 KB
testcase_29	AC	960 ms 24,412 KB
testcase_30	AC	1,006 ms 24,412 KB
testcase_31	AC	1,067 ms 24,416 KB
testcase_32	TLE	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

func main() {
	// https://yukicoder.me/problems/no/880
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, q int
	fmt.Fscan(in, &n, &q)
	nums := make([]E, n)
	for i := 0; i < n; i++ {
		var tmp int
		fmt.Fscan(in, &tmp)
		nums[i] = NewE(tmp)
	}

	seg := NewSegmentTreeBeats(nums)
	for i := 0; i < q; i++ {
		var t, l, r, x int
		fmt.Fscan(in, &t, &l, &r)
		l--
		if t <= 2 {
			fmt.Fscan(in, &x)
			if t == 1 {
				seg.Update(l, r, Id{updVal: x}) // RangeAssign
			} else {
				seg.Update(l, r, Id{gcdVal: x}) // RangeUpdateGcd
			}
		} else {
			res := seg.Query(l, r)
			if t == 3 {
				fmt.Fprintln(out, res.max) // RangeMax
			} else {
				fmt.Fprintln(out, res.sum) // RangeSum
			}
		}
	}

}

const INF int = 2e9

type E struct {
	sum, max, lcm, size int
	fail                bool
}

func NewE(v int) E {
	return E{
		sum:  v,
		max:  v,
		lcm:  v,
		size: 1,
	}
}

type Id struct{ updVal, gcdVal int }

func (*SegmentTreeBeats) e() E   { return E{lcm: 1} }
func (*SegmentTreeBeats) id() Id { return Id{} }
func (*SegmentTreeBeats) op(x, y E) E {
	return E{
		sum:  x.sum + y.sum,
		max:  max(x.max, y.max),
		lcm:  min(lcm(x.lcm, y.lcm), INF),
		size: x.size + y.size,
	}
}

func (*SegmentTreeBeats) mapping(f Id, x E) E {
	if f.updVal != 0 {
		return E{
			sum:  f.updVal * x.size,
			max:  f.updVal,
			lcm:  f.updVal,
			size: x.size,
		}
	}
	if f.gcdVal != 0 {
		if x.size == 1 {
			v := gcd(x.max, f.gcdVal)
			return E{
				sum:  v,
				max:  v,
				lcm:  v,
				size: 1,
			}
		} else if f.gcdVal%x.lcm != 0 {
			x.fail = true // !Special
		}
	}
	return x
}

func (*SegmentTreeBeats) composition(f, g Id) Id {
	if f.updVal != 0 {
		return f
	}
	if g.updVal != 0 {
		return Id{updVal: gcd(g.updVal, f.gcdVal)}
	}
	return Id{gcdVal: gcd(f.gcdVal, g.gcdVal)}
}

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

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}

//
//
//
//
// !template
type SegmentTreeBeats struct {
	n    int
	log  int
	size int
	data []E
	lazy []Id
}

func NewSegmentTreeBeats(
	leaves []E,
) *SegmentTreeBeats {
	tree := &SegmentTreeBeats{}
	n := int(len(leaves))
	tree.n = n
	tree.log = int(bits.Len(uint(n - 1)))
	tree.size = 1 << tree.log
	tree.data = make([]E, 2*tree.size)
	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 *SegmentTreeBeats) 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 *SegmentTreeBeats) QueryAll() E {
	return tree.data[1]
}

// 更新切片[left:right]的值
//   0<=left<=right<=len(tree.data)
func (tree *SegmentTreeBeats) 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 *SegmentTreeBeats) 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*2 + 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 *SegmentTreeBeats) 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%2 == 0 {
			left >>= 1
		}
		if !predicate(tree.op(res, tree.data[left])) {
			for left < tree.size {
				tree.pushDown(left)
				left *= 2
				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 *SegmentTreeBeats) Get(index int) E {
	index += tree.size
	for i := tree.log; i >= 1; i-- {
		tree.pushDown(index >> i)
	}
	return tree.data[index]
}

// 单点赋值
func (tree *SegmentTreeBeats) 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 *SegmentTreeBeats) pushUp(root int) {
	tree.data[root] = tree.op(tree.data[2*root], tree.data[2*root+1])
}

func (tree *SegmentTreeBeats) pushDown(root int) {
	if tree.lazy[root] != tree.id() {
		tree.propagate(2*root, tree.lazy[root])
		tree.propagate(2*root+1, tree.lazy[root])
		tree.lazy[root] = tree.id()
	}
}

func (tree *SegmentTreeBeats) propagate(root int, f Id) {
	tree.data[root] = tree.mapping(f, tree.data[root])
	if root < tree.size {
		tree.lazy[root] = tree.composition(f, tree.lazy[root])
		// !Special
		if tree.data[root].fail {
			tree.pushDown(root)
			tree.pushUp(root)
		}
	}
}