vnoj/go/qmax2.go

package main

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

type SegmentTree struct {
	n    int
	tree []int
	lazy []int
}

func NewSegmentTree(size int) *SegmentTree {
	tree := make([]int, 4*size)
	lazy := make([]int, 4*size)
	return &SegmentTree{size, tree, lazy}
}

func (st *SegmentTree) push(node, l, r int) {
	if st.lazy[node] != 0 {
		st.tree[node] += st.lazy[node]
		if l != r {
			st.lazy[node*2] += st.lazy[node]
			st.lazy[node*2+1] += st.lazy[node]
		}
		st.lazy[node] = 0
	}
}

func (st *SegmentTree) update(node, l, r, ul, ur, val int) {
	st.push(node, l, r)
	if r < ul || l > ur {
		return
	}
	if ul <= l && r <= ur {
		st.lazy[node] += val
		st.push(node, l, r)
		return
	}
	mid := (l + r) / 2
	st.update(node*2, l, mid, ul, ur, val)
	st.update(node*2+1, mid+1, r, ul, ur, val)
	if st.tree[node*2] > st.tree[node*2+1] {
		st.tree[node] = st.tree[node*2]
	} else {
		st.tree[node] = st.tree[node*2+1]
	}
}

func (st *SegmentTree) query(node, l, r, ql, qr int) int {
	st.push(node, l, r)
	if r < ql || l > qr {
		return -1 << 60
	}
	if ql <= l && r <= qr {
		return st.tree[node]
	}
	mid := (l + r) / 2
	left := st.query(node*2, l, mid, ql, qr)
	right := st.query(node*2+1, mid+1, r, ql, qr)
	if left > right {
		return left
	}
	return right
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m int
	fmt.Fscan(in, &n, &m)

	st := NewSegmentTree(n)

	for i := 0; i < m; i++ {
		var t, x, y, k int
		fmt.Fscan(in, &t, &x, &y)
		x--
		y--
		if t == 0 {
			fmt.Fscan(in, &k)
			st.update(1, 0, n-1, x, y, k)
		} else {
			res := st.query(1, 0, n-1, x, y)
			fmt.Fprintln(out, res)
		}
	}
}