GCJ/2008/1C/C/segment_tree.go

package main

// SegmentTree ...
type SegmentTree []int

// NewSegmentTree ...
func NewSegmentTree(a []int) (st SegmentTree) {
	n := len(a)
	st = make([]int, 2*n)
	copy(st[n:], a)
	for i := n - 1; 0 < i; i-- {
		st[i] = maxInt(st[2*i], st[2*i+1])
	}
	return
}

// NextGreater ...
func (st SegmentTree) NextGreater(val, i int) int {
	n := len(st) / 2
	beg, end := i+n, 2*n
	if end <= beg {
		return -1
	}
	for ; st[beg] <= val && beg < end; beg, end = beg/2, end/2 {
		if beg%2 == 1 {
			beg++
		}
		if end%2 == 1 {
			end--
		}
	}
	if st[beg] <= val {
		return -1
	}
	for beg < n {
		if val < st[2*beg] {
			beg = 2 * beg
		} else {
			beg = 2*beg + 1
		}
	}
	if beg-n < i {
		return -1
	}
	return beg - n
}