#968980 (Go) No.2012 Largest Triangle

提出ソース
結果

問題	No.2012 Largest Triangle
ユーザー	草苺奶昔
提出日時	2024-04-04 02:50:44
言語	Go (1.22.1)
結果	AC
実行時間	807 ms / 2,500 ms
コード長	18,750 bytes
コンパイル時間	14,242 ms
コンパイル使用メモリ	233,744 KB
実行使用メモリ	18,060 KB
最終ジャッジ日時	2024-10-01 00:14:08
合計ジャッジ時間	20,850 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	1 ms 6,820 KB
testcase_03	AC	1 ms 6,816 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	1 ms 6,816 KB
testcase_06	AC	1 ms 6,820 KB
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	1 ms 6,816 KB
testcase_10	AC	1 ms 6,820 KB
testcase_11	AC	2 ms 6,820 KB
testcase_12	AC	2 ms 6,816 KB
testcase_13	AC	2 ms 6,816 KB
testcase_14	AC	2 ms 6,816 KB
testcase_15	AC	2 ms 6,820 KB
testcase_16	AC	183 ms 14,300 KB
testcase_17	AC	170 ms 14,312 KB
testcase_18	AC	157 ms 14,300 KB
testcase_19	AC	155 ms 14,308 KB
testcase_20	AC	153 ms 14,300 KB
testcase_21	AC	150 ms 14,304 KB
testcase_22	AC	160 ms 14,304 KB
testcase_23	AC	158 ms 14,308 KB
testcase_24	AC	154 ms 14,304 KB
testcase_25	AC	156 ms 14,304 KB
testcase_26	AC	776 ms 17,132 KB
testcase_27	AC	784 ms 17,080 KB
testcase_28	AC	807 ms 17,016 KB
testcase_29	AC	805 ms 17,012 KB
testcase_30	AC	799 ms 18,060 KB
testcase_31	AC	484 ms 17,488 KB
testcase_32	AC	479 ms 16,328 KB
testcase_33	AC	463 ms 16,456 KB
testcase_34	AC	483 ms 16,900 KB
testcase_35	AC	502 ms 17,172 KB
testcase_36	AC	3 ms 6,820 KB
testcase_37	AC	3 ms 6,816 KB
testcase_38	AC	3 ms 6,820 KB
testcase_39	AC	3 ms 6,820 KB
testcase_40	AC	3 ms 6,816 KB
testcase_41	AC	150 ms 16,912 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 注意cpp里的迭代器:
// !Begin指向第一个元素,
// !End指向最后一个元素的下一个位置,
// 这里的迭代器设计为:
// !Begin指向第一个元素的前一个位置,First指向第一个元素
// !Last指向最后一个元素,End指向最后一个元素的下一个位置

// https://maspypy.github.io/library/convex/cht.hpp

// 在 C++ 中，long double 类型不等同于 float64。
// !long double 是一种浮点数类型，具有比 double 类型更高的精度和范围 (18位)。
// int 通常对应于 C++ 中的 double 类型，而非 long double 类型。
// long double 类型的精度和范围因编译器和平台而异。
// 在某些实现中，long double 可能与 double 类型具有相同的精度，
// 而在其他实现中，它可能具有更高的精度。
// 例如，在 x86 和 x86_64 架构上，long double 通常具有 80 位的扩展精度。

package main

import (
	"bufio"
	"fmt"
	stdio "io"
	"math/bits"
	"os"
	"sort"
	"strconv"
	"strings"
	"time"
)

// from https://atcoder.jp/users/ccppjsrb
var io *Iost

type Iost struct {
	Scanner *bufio.Scanner
	Writer  *bufio.Writer
}

func NewIost(fp stdio.Reader, wfp stdio.Writer) *Iost {
	const BufSize = 2000005
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, BufSize), BufSize)
	return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)}
}
func (io *Iost) Text() string {
	if !io.Scanner.Scan() {
		panic("scan failed")
	}
	return io.Scanner.Text()
}
func (io *Iost) Atoi(s string) int                 { x, _ := strconv.Atoi(s); return x }
func (io *Iost) Atoi64(s string) int64             { x, _ := strconv.ParseInt(s, 10, 64); return x }
func (io *Iost) Atof64(s string) float64           { x, _ := strconv.ParseFloat(s, 64); return x }
func (io *Iost) NextInt() int                      { return io.Atoi(io.Text()) }
func (io *Iost) NextInt64() int64                  { return io.Atoi64(io.Text()) }
func (io *Iost) NextFloat64() float64              { return io.Atof64(io.Text()) }
func (io *Iost) Print(x ...interface{})            { fmt.Fprint(io.Writer, x...) }
func (io *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(io.Writer, s, x...) }
func (io *Iost) Println(x ...interface{})          { fmt.Fprintln(io.Writer, x...) }

func main() {
	最大三角形面积()
	// abc244_h()
}

func abc244_h() {
	// https://atcoder.jp/contests/abc244/tasks/abc244_h
	// - 向点集中追加一个点(a,b), 表示为 a*x + b*y
	// - 查询 x=xi,y=yi 时的最大值
	in := os.Stdin
	out := os.Stdout
	io = NewIost(in, out)
	defer func() {
		io.Writer.Flush()
	}()

	q := io.NextInt()
	cht := NewLineContainer2D(q)
	for i := 0; i < q; i++ {
		a, b, x, y := io.NextInt(), io.NextInt(), io.NextInt(), io.NextInt()
		cht.Add(a, b)
		io.Println(cht.QueryMax(x, y))
	}
}

func 最大三角形面积() {
	// https://yukicoder.me/problems/no/2012
	// 平面上有n个点, 问最其中两点和原点组成的三角形的最大面积的2倍
	// !将(a,-b)加入点集，对每个点(x,y)查询最大的a*y-b*x
	in := os.Stdin
	out := os.Stdout
	io = NewIost(in, out)
	defer func() {
		io.Writer.Flush()
	}()

	n := io.NextInt()
	points := make([][2]int, n)
	for i := 0; i < n; i++ {
		points[i] = [2]int{io.NextInt(), io.NextInt()}
	}

	cht := NewLineContainer2D(n)
	for _, p := range points {
		a, b := p[0], p[1]
		cht.Add(a, -b)
	}

	res := 0
	for _, p := range points {
		x, y := p[0], p[1]
		res = max(res, cht.QueryMax(y, x))
	}
	io.Println(res)
}

const INF int = 1e18

type Line struct {
	k, b   int
	p1, p2 int // p=p1/p2
}

type LineContainer2D struct {
	minCHT, maxCHT *_LineContainer
	kMax, kMin     int
	bMax, bMin     int
}

func NewLineContainer2D(capacity int) *LineContainer2D {
	return &LineContainer2D{
		minCHT: _NewLineContainer(true, capacity),
		maxCHT: _NewLineContainer(false, capacity),
		kMax:   -INF,
		kMin:   INF,
		bMax:   -INF,
		bMin:   INF,
	}
}

// 追加 a*x + b*y.
func (lc *LineContainer2D) Add(a, b int) {
	lc.minCHT.Add(b, a)
	lc.maxCHT.Add(b, a)
	lc.kMax = max(lc.kMax, a)
	lc.kMin = min(lc.kMin, a)
	lc.bMax = max(lc.bMax, b)
	lc.bMin = min(lc.bMin, b)
}

// 查询 x=xi,y=yi 时的最大值 max_{a,b} (ax + by).
func (lc *LineContainer2D) QueryMax(x, y int) int {
	if lc.minCHT.Size() == 0 {
		return -INF
	}

	if x == 0 {
		if y > 0 {
			return lc.bMax * y
		}
		return lc.bMin * y
	}
	if y == 0 {
		if x > 0 {
			return lc.kMax * x
		}
		return lc.kMin * x
	}

	// y/x
	if x > 0 {
		l := lc.maxCHT.sl.BisectLeftByPair(y, x)
		line := lc.maxCHT.sl.At(l)
		a := line.b
		b := line.k
		return a*x + b*y
	}
	l := lc.minCHT.sl.BisectLeftByPair(y, x)
	line := lc.minCHT.sl.At(l)
	a := -line.b
	b := -line.k
	return a*x + b*y
}

// 查询 x=xi,y=yi 时的最小值 min_{a,b} (ax + by).
func (lc *LineContainer2D) QueryMin(x, y int) int { return -lc.QueryMax(-x, -y) }

type _LineContainer struct {
	minimize bool
	sl       *SpecializedSortedList
}

func _NewLineContainer(minimize bool, capacity int) *_LineContainer {
	return &_LineContainer{
		minimize: minimize,
		sl:       NewSpecializedSortedList(func(a, b *Line) bool { return a.k < b.k }),
	}
}

func (lc *_LineContainer) Add(k, m int) {
	if lc.minimize {
		k, m = -k, -m
	}

	newLine := &Line{k: k, b: m}
	lc.sl.Add(newLine)
	it1 := lc.sl.BisectRightByK(newLine.k) - 1
	it2 := it1
	line2 := lc.sl.At(it2)
	it1++
	it3 := it2
	for lc.insect(line2, lc.sl.At(it1)) {
		lc.sl.Pop(it1)
	}

	if it3 != 0 {
		it3--
		line3 := lc.sl.At(it3)
		if lc.insect(line3, line2) {
			lc.sl.Pop(it2)
			lc.insect(line3, lc.sl.At(it2))
		}
	}

	if it3 == 0 {
		return
	}

	dp1, dp2 := lc.sl.At(it3-1), lc.sl.At(it3)
	for it3 != 0 {
		it2 := it3
		if lessPair(dp1.p1, dp1.p2, dp2.p1, dp2.p2) {
			break
		}
		it3--
		lc.sl.Pop(it2)
		lc.insect(dp1, lc.sl.At(it2))
		dp1, dp2 = lc.sl.At(it3-1), dp1
	}
}

// 查询 kx + m 的最小值（或最大值).
func (lc *_LineContainer) Query(x int) int {
	if lc.sl.Len() == 0 {
		panic("empty container")
	}
	pos := lc.sl.BisectLeftByPair(x, 1)
	line := lc.sl.At(pos)
	v := line.k*x + line.b
	if lc.minimize {
		return -v
	}
	return v
}

func (lc *_LineContainer) Size() int32 { return lc.sl.Len() }

// 这个函数在向集合添加新线或删除旧线时用于计算交点。
// 计算线性函数x和y的交点，并将结果存储在x->p中。
func (lc *_LineContainer) insect(line1, line2 *Line) bool {
	if line2 == nil {
		line1.p1 = INF
		line1.p2 = 1
		return false
	}
	if line1.k == line2.k {
		if line1.b > line2.b {
			line1.p1 = INF
			line1.p2 = 1
		} else {
			line1.p1 = INF
			line1.p2 = -1
		}
	} else {
		// lc_div
		line1.p1 = line2.b - line1.b
		line1.p2 = line1.k - line2.k
	}
	return !lessPair(line1.p1, line1.p2, line2.p1, line2.p2)
}

type _Value = *Line

type _node struct {
	left, right int32
	size        int32
	priority    uint64
	value       _Value
}

type _SL struct {
	seed  uint64
	root  int32
	nodes []_node
}

func _NSL(initCapacity int) *_SL {
	sl := &_SL{
		seed:  uint64(time.Now().UnixNano()/2 + 1),
		nodes: make([]_node, 0, max(initCapacity, 16)),
	}
	dummy := &_node{size: 0, priority: sl.nextRand(), value: &Line{p2: 1}} // dummy node 0
	sl.nodes = append(sl.nodes, *dummy)
	return sl
}

func (sl *_SL) pushUp(root int32) {
	sl.nodes[root].size = sl.nodes[sl.nodes[root].left].size + sl.nodes[sl.nodes[root].right].size + 1
}

func (sl *_SL) Add(value _Value) {
	var x, y, z int32
	sl.splitByValue(sl.root, value.k, &x, &y, false)
	z = sl.newNode(value)
	sl.root = sl.merge(sl.merge(x, z), y)
}

func (sl *_SL) At(index int32) _Value {
	if index < 0 || index >= sl.Len() {
		return nil
	}
	return sl.nodes[sl.kthNode(sl.root, index+1)].value
}

func (sl *_SL) Pop(index int32) _Value {
	index += 1 // dummy offset
	var x, y, z int32
	sl.splitByRank(sl.root, index, &y, &z)
	sl.splitByRank(y, index-1, &x, &y)
	res := sl.nodes[y].value
	sl.root = sl.merge(x, z)
	return res
}

func (sl *_SL) BisectLeft(k int) int32 {
	var x, y int32
	sl.splitByValue(sl.root, k, &x, &y, true)
	res := sl.nodes[x].size
	sl.root = sl.merge(x, y)
	return res
}

func (sl *_SL) BisectLeftByPair(a, b int) int32 {
	var x, y int32
	sl.splitByValueWith(sl.root, a, b, &x, &y)
	res := sl.nodes[x].size
	sl.root = sl.merge(x, y)
	return res
}

func (sl *_SL) BisectRightByK(k int) int32 {
	var x, y int32
	sl.splitByValue(sl.root, k, &x, &y, false)
	res := sl.nodes[x].size
	sl.root = sl.merge(x, y)
	return res
}

func (sl *_SL) String() string {
	sb := []string{"SortedList{"}
	values := []string{}
	for i := int32(0); i < sl.Len(); i++ {
		values = append(values, fmt.Sprintf("%v", sl.At(i)))
	}
	sb = append(sb, strings.Join(values, ","), "}")
	return strings.Join(sb, "")
}

func (sl *_SL) Len() int32 {
	return sl.nodes[sl.root].size
}

func (sl *_SL) kthNode(root int32, k int32) int32 {
	cur := root
	for cur != 0 {
		if sl.nodes[sl.nodes[cur].left].size+1 == k {
			break
		} else if sl.nodes[sl.nodes[cur].left].size >= k {
			cur = sl.nodes[cur].left
		} else {
			k -= sl.nodes[sl.nodes[cur].left].size + 1
			cur = sl.nodes[cur].right
		}
	}
	return cur
}

func (sl *_SL) splitByValue(root int32, k int, x, y *int32, strictLess bool) {
	if root == 0 {
		*x, *y = 0, 0
		return
	}
	if strictLess {
		if sl.nodes[root].value.k < k {
			*x = root
			sl.splitByValue(sl.nodes[root].right, k, &sl.nodes[root].right, y, strictLess)
		} else {
			*y = root
			sl.splitByValue(sl.nodes[root].left, k, x, &sl.nodes[root].left, strictLess)
		}
	} else {
		if sl.nodes[root].value.k <= k {
			*x = root
			sl.splitByValue(sl.nodes[root].right, k, &sl.nodes[root].right, y, strictLess)
		} else {
			*y = root
			sl.splitByValue(sl.nodes[root].left, k, x, &sl.nodes[root].left, strictLess)
		}
	}
	sl.pushUp(root)
}

func (sl *_SL) splitByValueWith(root int32, a1, b1 int, x, y *int32) {
	if root == 0 {
		*x, *y = 0, 0
		return
	}
	a2, b2 := sl.nodes[root].value.p1, sl.nodes[root].value.p2
	if lessPair(a2, b2, a1, b1) {
		*x = root
		sl.splitByValueWith(sl.nodes[root].right, a1, b1, &sl.nodes[root].right, y)
	} else {
		*y = root
		sl.splitByValueWith(sl.nodes[root].left, a1, b1, x, &sl.nodes[root].left)
	}
	sl.pushUp(root)
}

// 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 (sl *_SL) splitByRank(root, k int32, x, y *int32) {
	if root == 0 {
		*x, *y = 0, 0
		return
	}
	if k <= sl.nodes[sl.nodes[root].left].size {
		*y = root
		sl.splitByRank(sl.nodes[root].left, k, x, &sl.nodes[root].left)
		sl.pushUp(*y)
	} else {
		*x = root
		sl.splitByRank(sl.nodes[root].right, k-sl.nodes[sl.nodes[root].left].size-1, &sl.nodes[root].right, y)
		sl.pushUp(*x)
	}
}

func (sl *_SL) merge(x, y int32) int32 {
	if x == 0 || y == 0 {
		return x + y
	}
	if sl.nodes[x].priority < sl.nodes[y].priority {
		sl.nodes[x].right = sl.merge(sl.nodes[x].right, y)
		sl.pushUp(x)
		return x
	}
	sl.nodes[y].left = sl.merge(x, sl.nodes[y].left)
	sl.pushUp(y)
	return y
}

func (sl *_SL) newNode(value _Value) int32 {
	sl.nodes = append(sl.nodes, _node{
		value:    value,
		size:     1,
		priority: sl.nextRand(),
	})
	return int32(len(sl.nodes) - 1)
}

// https://nyaannyaan.github.io/library/misc/rng.hpp
func (sl *_SL) nextRand() uint64 {
	sl.seed ^= sl.seed << 7
	sl.seed ^= sl.seed >> 9
	return sl.seed
}

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
}

// 分母不为0的分数比较大小
//
//	a1/b1 < a2/b2
func lessPair(a1, b1, a2, b2 int) bool {
	if a1 == INF || a2 == INF { // 有一个是+-INF
		return a1/b1 < a2/b2
	}
	diff := a1*b2 - a2*b1
	mul := b1 * b2
	return diff^mul < 0
}

const _LOAD int32 = 100 // 75/100/150/200

type S = *Line

type SpecializedSortedList struct {
	less              func(a, b S) bool
	size              int32
	blocks            [][]S
	mins              []S
	tree              []int32
	shouldRebuildTree bool
}

func NewSpecializedSortedList(less func(a, b S) bool, elements ...S) *SpecializedSortedList {
	elements = append(elements[:0:0], elements...)
	res := &SpecializedSortedList{less: less}
	sort.Slice(elements, func(i, j int) bool { return less(elements[i], elements[j]) })
	n := int32(len(elements))
	blocks := [][]S{}
	for start := int32(0); start < n; start += _LOAD {
		end := min32(start+_LOAD, n)
		blocks = append(blocks, elements[start:end:end]) // !各个块互不影响, max参数也需要指定为end
	}
	mins := make([]S, len(blocks))
	for i, cur := range blocks {
		mins[i] = cur[0]
	}
	res.size = n
	res.blocks = blocks
	res.mins = mins
	res.shouldRebuildTree = true
	return res
}

func (sl *SpecializedSortedList) Add(value S) *SpecializedSortedList {
	sl.size++
	if len(sl.blocks) == 0 {
		sl.blocks = append(sl.blocks, []S{value})
		sl.mins = append(sl.mins, value)
		sl.shouldRebuildTree = true
		return sl
	}

	pos, index := sl._locRight(value)

	sl._updateTree(pos, 1)
	sl.blocks[pos] = append(sl.blocks[pos][:index], append([]S{value}, sl.blocks[pos][index:]...)...)
	sl.mins[pos] = sl.blocks[pos][0]

	// n -> load + (n - load)
	if n := int32(len(sl.blocks[pos])); _LOAD+_LOAD < n {
		sl.blocks = append(sl.blocks[:pos+1], append([][]S{sl.blocks[pos][_LOAD:]}, sl.blocks[pos+1:]...)...)
		sl.mins = append(sl.mins[:pos+1], append([]S{sl.blocks[pos][_LOAD]}, sl.mins[pos+1:]...)...)
		sl.blocks[pos] = sl.blocks[pos][:_LOAD:_LOAD] // !注意max的设置(为了让左右互不影响)
		sl.shouldRebuildTree = true
	}

	return sl
}

func (sl *SpecializedSortedList) Pop(index int32) S {
	if index < 0 {
		index += sl.size
	}
	if index < 0 || index >= sl.size {
		panic("index out of range")
	}
	pos, startIndex := sl._findKth(index)
	value := sl.blocks[pos][startIndex]
	sl._delete(pos, startIndex)
	return value
}

func (sl *SpecializedSortedList) At(index int32) S {
	if index < 0 {
		index += sl.size
	}
	if index < 0 || index >= sl.size {
		return nil
	}
	pos, startIndex := sl._findKth(index)
	return sl.blocks[pos][startIndex]
}

func (sl *SpecializedSortedList) BisectRightByK(k int) int32 {
	pos, index := sl._locRightByK(k)
	return sl._queryTree(pos) + index
}

func (sl *SpecializedSortedList) BisectLeftByPair(a, b int) int32 {
	pos, index := sl._locLeftByPair(a, b)
	return sl._queryTree(pos) + index
}

func (sl *SpecializedSortedList) Clear() {
	sl.size = 0
	sl.blocks = sl.blocks[:0]
	sl.mins = sl.mins[:0]
	sl.tree = sl.tree[:0]
	sl.shouldRebuildTree = true
}

func (sl *SpecializedSortedList) Len() int32 {
	return sl.size
}

func (sl *SpecializedSortedList) _delete(pos, index int32) {
	// !delete element
	sl.size--
	sl._updateTree(pos, -1)
	sl.blocks[pos] = append(sl.blocks[pos][:index], sl.blocks[pos][index+1:]...)
	if len(sl.blocks[pos]) > 0 {
		sl.mins[pos] = sl.blocks[pos][0]
		return
	}

	// !delete block
	sl.blocks = append(sl.blocks[:pos], sl.blocks[pos+1:]...)
	sl.mins = append(sl.mins[:pos], sl.mins[pos+1:]...)
	sl.shouldRebuildTree = true
}

func (sl *SpecializedSortedList) _locLeft(value S) (pos, index int32) {
	if sl.size == 0 {
		return
	}

	// find pos
	left := int32(-1)
	right := int32(len(sl.blocks) - 1)
	for left+1 < right {
		mid := (left + right) >> 1
		if !sl.less(sl.mins[mid], value) {
			right = mid
		} else {
			left = mid
		}
	}
	if right > 0 {
		block := sl.blocks[right-1]
		if !sl.less(block[len(block)-1], value) {
			right--
		}
	}
	pos = right

	// find index
	cur := sl.blocks[pos]
	left = -1
	right = int32(len(cur))
	for left+1 < right {
		mid := (left + right) >> 1
		if !sl.less(cur[mid], value) {
			right = mid
		} else {
			left = mid
		}
	}

	index = right
	return
}

func (sl *SpecializedSortedList) _locLeftByPair(a, b int) (pos, index int32) {
	if sl.size == 0 {
		return
	}

	// find pos
	left := int32(-1)
	right := int32(len(sl.blocks) - 1)
	for left+1 < right {
		mid := (left + right) >> 1
		if !lessPair(sl.mins[mid].p1, sl.mins[mid].p2, a, b) {
			right = mid
		} else {
			left = mid
		}
	}
	if right > 0 {
		block := sl.blocks[right-1]
		last := block[len(block)-1]
		if !lessPair(last.p1, last.p2, a, b) {
			right--
		}
	}
	pos = right

	// find index
	cur := sl.blocks[pos]
	left = -1
	right = int32(len(cur))
	for left+1 < right {
		mid := (left + right) >> 1
		if !lessPair(cur[mid].p1, cur[mid].p2, a, b) {
			right = mid
		} else {
			left = mid
		}
	}

	index = right
	return
}

func (sl *SpecializedSortedList) _locRight(value S) (pos, index int32) {
	if sl.size == 0 {
		return
	}

	// find pos
	left := int32(0)
	right := int32(len(sl.blocks))
	for left+1 < right {
		mid := (left + right) >> 1
		if sl.less(value, sl.mins[mid]) {
			right = mid
		} else {
			left = mid
		}
	}
	pos = left

	// find index
	cur := sl.blocks[pos]
	left = -1
	right = int32(len(cur))
	for left+1 < right {
		mid := (left + right) >> 1
		if sl.less(value, cur[mid]) {
			right = mid
		} else {
			left = mid
		}
	}

	index = right
	return
}

func (sl *SpecializedSortedList) _locRightByK(k int) (pos, index int32) {
	if sl.size == 0 {
		return
	}

	// find pos
	left := int32(0)
	right := int32(len(sl.blocks))
	for left+1 < right {
		mid := (left + right) >> 1
		if k < sl.mins[mid].k {
			right = mid
		} else {
			left = mid
		}
	}
	pos = left

	// find index
	cur := sl.blocks[pos]
	left = -1
	right = int32(len(cur))
	for left+1 < right {
		mid := (left + right) >> 1
		if k < cur[mid].k {
			right = mid
		} else {
			left = mid
		}
	}

	index = right
	return
}

func (sl *SpecializedSortedList) _buildTree() {
	sl.tree = make([]int32, len(sl.blocks))
	for i := 0; i < len(sl.blocks); i++ {
		sl.tree[i] = int32(len(sl.blocks[i]))
	}
	tree := sl.tree
	for i := 0; i < len(tree); i++ {
		j := i | (i + 1)
		if j < len(tree) {
			tree[j] += tree[i]
		}
	}
	sl.shouldRebuildTree = false
}

func (sl *SpecializedSortedList) _updateTree(index, delta int32) {
	if sl.shouldRebuildTree {
		return
	}
	tree := sl.tree
	for i := index; i < int32(len(tree)); i |= i + 1 {
		tree[i] += delta
	}
}

func (sl *SpecializedSortedList) _queryTree(end int32) int32 {
	if sl.shouldRebuildTree {
		sl._buildTree()
	}
	tree := sl.tree
	sum := int32(0)
	for end > 0 {
		sum += tree[end-1]
		end &= end - 1
	}
	return sum
}

func (sl *SpecializedSortedList) _findKth(k int32) (pos, index int32) {
	if k < int32(len(sl.blocks[0])) {
		return 0, k
	}
	last := int32(len(sl.blocks) - 1)
	lastLen := int32(len(sl.blocks[last]))
	if k >= sl.size-lastLen {
		return last, k + lastLen - sl.size
	}
	if sl.shouldRebuildTree {
		sl._buildTree()
	}
	tree := sl.tree
	pos = -1
	m := int32(len(tree))
	bitLength := bits.Len32(uint32(m))
	for d := bitLength - 1; d >= 0; d-- {
		next := pos + (1 << d)
		if next < m && k >= tree[next] {
			pos = next
			k -= tree[pos]
		}
	}
	return pos + 1, k
}

func min32(a, b int32) int32 {
	if a < b {
		return a
	}
	return b
}