diff options
| -rw-r--r-- | sd.go | 43 |
1 files changed, 41 insertions, 2 deletions
@@ -9,6 +9,45 @@ import ( var file = flag.String("f", "cards", "cards file") +var seg = []int{} + +func build(a *[]int, l int, r int, n int) { + if l == r { + seg[n] = (*a)[l] + return + } + m := (l + r) >> 1 + build(a, l, m, n<<1) + build(a, m+1, r, n<<1|1) + seg[n] = seg[n<<1] + seg[n<<1|1] +} + +func update(x int, v int, l int, r int, n int) { + if l == r { + seg[n] += v + return + } + m := (l + r) >> 1 + if x <= m { + update(x, v, l, m, n<<1) + } else { + update(x, v, m+1, r, n<<1|1) + } + seg[n] = seg[n<<1] + seg[n<<1|1] +} + +func query(v int, l int, r int, n int) (int, int) { + if l == r { + return seg[n], n + } + m := (l + r) >> 1 + if seg[n<<1] < v { + return query(v, l, m, n<<1) + } else { + return query(v-seg[n<<1], m+1, r, n<<1|1) + } +} + func main() { flag.Parse() @@ -22,7 +61,7 @@ func main() { for { fmt.Println("hello world") - + var b []byte = make([]byte, 1) os.Stdin.Read(b) if string(b) == 'y' { @@ -30,7 +69,7 @@ func main() { } else if string(b) == 'n' { } else { - + } } } |