EXTRA: 查询 [l,r] 上小于 v 的最靠左的位置 这里线段树维护的是区间最小值 不存在时返回 0
(o, l, r, v int)
| 146 | // 这里线段树维护的是区间最小值 |
| 147 | // 不存在时返回 0 |
| 148 | func (t seg) queryFirstLessPosInRange(o, l, r, v int) int { |
| 149 | if t[o].val >= v { |
| 150 | return 0 |
| 151 | } |
| 152 | if t[o].l == t[o].r { |
| 153 | return t[o].l |
| 154 | } |
| 155 | m := (t[o].l + t[o].r) >> 1 |
| 156 | if l <= m { |
| 157 | if pos := t.queryFirstLessPosInRange(o<<1, l, r, v); pos > 0 { |
| 158 | return pos |
| 159 | } |
| 160 | } |
| 161 | if m < r { |
| 162 | if pos := t.queryFirstLessPosInRange(o<<1|1, l, r, v); pos > 0 { |
| 163 | return pos |
| 164 | } |
| 165 | } |
| 166 | return 0 |
| 167 | } |
| 168 | |
| 169 | // |
| 170 |
nothing calls this directly
no outgoing calls
no test coverage detected