#848857 (Go) No.1441 MErGe

• 問題: No.1441 MErGe
• ユーザー: 草苺奶昔
• 提出日時: 2023-03-13 21:09:03
• 言語: Go (1.22.1)
• 結果: AC
• 実行時間: 947 ms / 1,000 ms
• コード長: 8,300 bytes
• コンパイル時間: 10,641 ms
• コンパイル使用メモリ: 232,096 KB
• 実行使用メモリ: 104,508 KB
• 最終ジャッジ日時: 2024-09-18 07:45:04
• 合計ジャッジ時間: 27,720 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,816 KB
testcase_01	AC	1 ms; 6,812 KB
testcase_02	AC	1 ms; 6,940 KB
testcase_03	AC	5 ms; 6,940 KB
testcase_04	AC	6 ms; 6,940 KB
testcase_05	AC	16 ms; 6,940 KB
testcase_06	AC	17 ms; 6,944 KB
testcase_07	AC	17 ms; 6,940 KB
testcase_08	AC	177 ms; 11,772 KB
testcase_09	AC	177 ms; 11,776 KB
testcase_10	AC	316 ms; 13,888 KB
testcase_11	AC	285 ms; 13,884 KB
testcase_12	AC	312 ms; 13,868 KB
testcase_13	AC	800 ms; 54,996 KB
testcase_14	AC	828 ms; 55,004 KB
testcase_15	AC	854 ms; 52,952 KB
testcase_16	AC	788 ms; 52,904 KB
testcase_17	AC	770 ms; 52,936 KB
testcase_18	AC	485 ms; 30,344 KB
testcase_19	AC	537 ms; 34,468 KB
testcase_20	AC	420 ms; 28,280 KB
testcase_21	AC	381 ms; 24,156 KB
testcase_22	AC	550 ms; 26,264 KB
testcase_23	AC	940 ms; 59,144 KB
testcase_24	AC	947 ms; 59,140 KB
testcase_25	AC	917 ms; 59,140 KB
testcase_26	AC	931 ms; 59,140 KB
testcase_27	AC	934 ms; 59,140 KB
testcase_28	AC	831 ms; 104,508 KB
testcase_29	AC	828 ms; 104,508 KB

ソースコード

package main

import (
	"bufio"
	"fmt"
	"os"
	"runtime/debug"
	"strings"
)

func init() {
	debug.SetGCPercent(-1)
}
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

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

	arr := NewDynamicSequence(nums)
	for i := 0; i < q; i++ {
		var op, left, right int
		fmt.Fscan(in, &op, &left, &right)
		left--
		if op == 1 {
			sum := arr.Query(left, right)
			arr.Erase(left, right)
			arr.Insert(left, sum)
		} else {
			fmt.Fprintln(out, arr.Query(left, right))
		}
	}

}

type Node struct {
	// !Raw value
	element int

	// !Data and lazy tag maintained by segment tree
	sum     int
	lazyAdd int

	// FHQTreap inner attributes
	left, right int
	size        int
	isReversed  bool
}

// Add a new node and return its nodeId.
func (t *FHQTreap) newNode(data int) int {
	node := &Node{
		size:    1,
		element: data,
		sum:     data,
	}
	t.nodes = append(t.nodes, *node)
	return len(t.nodes) - 1
}

// !op
func (t *FHQTreap) pushUp(root int) {
	node := &t.nodes[root]
	// If left or right is 0(dummy), it will update with monoid.
	node.size = t.nodes[node.left].size + t.nodes[node.right].size + 1
	node.sum = t.nodes[node.left].sum + t.nodes[node.right].sum + node.element
}

// Reverse first and then push down the lazy tag.
func (t *FHQTreap) pushDown(root int) {
	node := &t.nodes[root]

	if node.isReversed {
		if node.left != 0 {
			t.toggle(node.left)
		}
		if node.right != 0 {
			t.toggle(node.right)
		}
		node.isReversed = false
	}

	if node.lazyAdd != 0 {
		delta := node.lazyAdd
		// !Not dummy node
		if node.left != 0 {
			t.propagate(node.left, delta)
		}
		if node.right != 0 {
			t.propagate(node.right, delta)
		}
		node.lazyAdd = 0
	}
}

// !mapping + composition
func (t *FHQTreap) propagate(root int, delta int) {
	node := &t.nodes[root]
	node.element += delta // need to update raw value (differs from segment tree)
	node.sum += delta * node.size
	node.lazyAdd += delta
}

type FHQTreap struct {
	x, y, z, w uint32
	root       int
	nodes      []Node
}

// Need to be modified according to the actual situation to implement a segment tree.
func NewDynamicSequence(nums []int) *FHQTreap {
	treap := &FHQTreap{
		x: 123456789, y: 362436069, z: 521288629, w: 88675123,
		nodes: make([]Node, 0, max(len(nums), 16)),
	}

	dummy := &Node{size: 0} // 0 is dummy
	treap.nodes = append(treap.nodes, *dummy)
	treap.root = treap.build(1, len(nums), nums)
	return treap
}

// Return the value at the k-th position (0-indexed).
func (t *FHQTreap) At(index int) int {
	n := t.Size()
	if index < 0 {
		index += n
	}

	if index < 0 || index >= n {
		panic(fmt.Sprintf("index %d out of range [0,%d]", index, n-1))
	}

	index++ // dummy offset
	var x, y, z int
	t.splitByRank(t.root, index, &y, &z)
	t.splitByRank(y, index-1, &x, &y)
	res := t.nodes[y].element
	t.root = t.merge(t.merge(x, y), z)
	return res
}

// Set the k-th position (0-indexed) to the given value.
func (t *FHQTreap) Set(index int, element int) {
	n := t.Size()
	if index < 0 {
		index += n
	}

	if index < 0 || index >= n {
		panic(fmt.Sprintf("index %d out of range [0,%d]", index, n-1))
	}

	index++ // dummy offset
	var x, y, z int
	t.splitByRank(t.root, index, &y, &z)
	t.splitByRank(y, index-1, &x, &y)
	t.nodes[y].element = element
	t.root = t.merge(t.merge(x, y), z)
}

// Reverse [start, stop) in place.
func (t *FHQTreap) Reverse(start, stop int) {
	var x, y, z int
	t.splitByRank(t.root, stop, &x, &z)
	t.splitByRank(x, start, &x, &y)
	t.toggle(y)
	t.root = t.merge(t.merge(x, y), z)
}

// Rotate [start, stop) to the right step times.
func (t *FHQTreap) RotateRight(start, stop, step int) {
	start++
	n := stop - start + 1 - step%(stop-start+1)
	var x, y, z, p int
	t.splitByRank(t.root, start-1, &x, &y)
	t.splitByRank(y, n, &y, &z)
	t.splitByRank(z, stop-start+1-n, &z, &p)
	t.root = t.merge(t.merge(t.merge(x, z), y), p)
}

// Append value to the end of the list.
func (t *FHQTreap) Append(value int) {
	t.Insert(t.Size(), value)
}

// Insert value before index.
func (t *FHQTreap) Insert(index int, value int) {
	n := t.Size()
	if index < 0 {
		index += n
	}

	var x, y int
	t.splitByRank(t.root, index, &x, &y)
	t.root = t.merge(t.merge(x, t.newNode(value)), y)
}

// Remove and return item at index.
func (t *FHQTreap) Pop(index int) int {
	n := t.Size()
	if index < 0 {
		index += n
	}

	index++ // dummy offset
	var x, y, z int
	t.splitByRank(t.root, index, &y, &z)
	t.splitByRank(y, index-1, &x, &y)
	res := &t.nodes[y].element
	t.root = t.merge(x, z)
	return *res
}

// Remove [start, stop) from list.
func (t *FHQTreap) Erase(start, stop int) {
	var x, y, z int
	start++ // dummy offset
	t.splitByRank(t.root, stop, &y, &z)
	t.splitByRank(y, start-1, &x, &y)
	t.root = t.merge(x, z)
}

// Update [start, stop) with value (defaults to range add).
//  0 <= start <= stop <= n
//  !alias:Apply
func (t *FHQTreap) Update(start, stop int, delta int) {
	start++
	var x, y, z int
	t.splitByRank(t.root, stop, &y, &z)
	t.splitByRank(y, start-1, &x, &y)
	t.propagate(y, delta)
	t.root = t.merge(t.merge(x, y), z)
}

// Query [start, stop) (defaults to range sum).
//  0 <= start <= stop <= n
func (t *FHQTreap) Query(start, stop int) int {
	start++
	var x, y, z int
	t.splitByRank(t.root, stop, &y, &z)
	t.splitByRank(y, start-1, &x, &y)
	res := t.nodes[y].sum
	t.root = t.merge(t.merge(x, y), z)
	return res
}

// Query [0, n) (defaults to range sum).
func (t *FHQTreap) QueryAll() int {
	return t.nodes[t.root].sum
}

// Return the number of items in the list.
func (t *FHQTreap) Size() int {
	return t.nodes[t.root].size
}

// Return all elements in index order.
func (t *FHQTreap) InOrder() []int {
	res := make([]int, 0, t.Size())
	t.inOrder(t.root, &res)
	return res
}

func (t *FHQTreap) inOrder(root int, res *[]int) {
	if root == 0 {
		return
	}
	t.pushDown(root) // !pushDown lazy tag
	t.inOrder(t.nodes[root].left, res)
	*res = append(*res, t.nodes[root].element)
	t.inOrder(t.nodes[root].right, res)
}

// Split by rank.
// Split the tree rooted at root into two trees, x and y, such that the size of x is k.
// x is the left subtree, y is the right subtree.
func (t *FHQTreap) splitByRank(root, k int, x, y *int) {
	if root == 0 {
		*x, *y = 0, 0
		return
	}

	t.pushDown(root)
	leftSize := t.nodes[t.nodes[root].left].size
	if leftSize+1 <= k {
		*x = root
		t.splitByRank(t.nodes[root].right, k-leftSize-1, &t.nodes[root].right, y)
		t.pushUp(*x)
	} else {
		*y = root
		t.splitByRank(t.nodes[root].left, k, x, &t.nodes[root].left)
		t.pushUp(*y)
	}
}

// Make sure that the height of the resulting tree is at most O(log n).
// A random priority is introduced to determine who is the root after merge operation.
// If left subtree is smaller, merge right subtree with the right child of the left subtree.
// Otherwise, merge left subtree with the left child of the right subtree.
func (t *FHQTreap) merge(x, y int) int {
	if x == 0 || y == 0 {
		return x + y
	}

	l, r := &t.nodes[x], &t.nodes[y]
	if t.fastRand()%uint32((l.size+r.size)) < uint32(l.size) {
		t.pushDown(x)
		l.right = t.merge(l.right, y)
		t.pushUp(x)
		return x
	} else {
		t.pushDown(y)
		r.left = t.merge(x, r.left)
		t.pushUp(y)
		return y
	}
}

// Build a treap from a slice and return the root nodeId. O(n).
func (t *FHQTreap) build(left, right int, nums []int) int {
	if left > right {
		return 0
	}
	mid := (left + right) >> 1
	newNode := t.newNode(nums[mid-1])
	t.nodes[newNode].left = t.build(left, mid-1, nums)
	t.nodes[newNode].right = t.build(mid+1, right, nums)
	t.pushUp(newNode)
	return newNode
}

func (t *FHQTreap) toggle(root int) {
	t.nodes[root].left, t.nodes[root].right = t.nodes[root].right, t.nodes[root].left
	t.nodes[root].isReversed = !t.nodes[root].isReversed
}

func (t *FHQTreap) String() string {
	sb := []string{"rbstarray{"}
	values := []string{}
	for i := 0; i < t.Size(); i++ {
		values = append(values, fmt.Sprintf("%d", t.At(i)))
	}
	sb = append(sb, strings.Join(values, ","), "}")
	return strings.Join(sb, "")
}

func (t *FHQTreap) fastRand() uint32 {
	tmp := t.x ^ (t.x << 11)
	t.x, t.y, t.z = t.y, t.z, t.w
	t.w = (t.w ^ (t.w >> 19)) ^ (tmp ^ (tmp >> 8))
	return t.w
}

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