結果
| 問題 |
No.2361 Many String Compare Queries
|
| コンテスト | |
| ユーザー |
 草苺奶昔
|
| 提出日時 | 2024-02-25 19:42:52 |
| 言語 | Go (1.23.4) |
| 結果 |
AC
|
| 実行時間 | 385 ms / 2,500 ms |
| コード長 | 21,352 bytes |
| コンパイル時間 | 19,129 ms |
| コンパイル使用メモリ | 235,820 KB |
| 実行使用メモリ | 135,060 KB |
| 最終ジャッジ日時 | 2024-09-29 11:08:36 |
| 合計ジャッジ時間 | 23,838 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 14 |
ソースコード
package main
import (
"bufio"
"fmt"
"index/suffixarray"
"os"
"reflect"
"sort"
"unsafe"
)
func main() {
// demo()
// cf123d()
// cf427d()
// cf802I()
// cf873F()
// P3181()
// p3804()
// p4341()
// p5341()
yukicoder2361()
}
// https://oi-wiki.org/string/suffix-tree/
func demo() {
// s := "cabab"
s := "abbbab"
sa, _, lcp := SuffixArray32(int32(len(s)), func(i int32) int32 { return int32(s[i]) })
suffixTree, ranges := SuffixTreeFrom(sa, lcp)
fmt.Println(suffixTree, ranges)
start, end := RecoverSubstring(sa, 3, 1, 3)
fmt.Println(s[start:end])
}
// CF123D String
// https://www.luogu.com.cn/problem/CF123D
// !枚举字符串 s 的每一个本质不同的子串 ss ，令 cnt(ss) 为子串 ss 在字符串 s 中出现的个数，求 ∑ cnt(ss)*(cnt(ss)+1)/2
// 建立后缀树，可以得到每个节点对应后缀数组上的 [行1，行2，列1，列2] 矩形区域.
// !(行2-行1) 表示此startPos出现次数, (列2-列1) 表示结点包含的压缩的字符串长度(个数).
func cf123d() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var s string
fmt.Fscan(in, &s)
_, ranges := SuffixTree(int32(len(s)), func(i int32) int32 { return int32(s[i]) })
res := 0
for i := 1; i < len(ranges); i++ {
rowStart, rowEnd, colStart, colEnd := ranges[i][0], ranges[i][1], ranges[i][2], ranges[i][3]
freq, nodeCount := int(rowEnd-rowStart), int(colEnd-colStart)
res += (freq * (freq + 1) / 2) * nodeCount
}
fmt.Fprintln(out, res)
}
// Match & Catch
// https://www.luogu.com.cn/problem/CF427D
// 求两个串的最短公共唯一子串
// 令s12 := s1 + "#" + s2，遍历后缀树，对每个结点统计belong即可.
func cf427d() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
const INF int32 = 1e9
var s1, s2 string
fmt.Fscan(in, &s1, &s2)
n1 := int32(len(s1))
s12 := s1 + "#" + s2
sa, _, height := SuffixArray32(int32(len(s12)), func(i int32) int32 { return int32(s12[i]) })
tree, ranges := SuffixTreeFrom(sa, height)
res := INF
var dfs func(cur int32)
dfs = func(cur int32) {
rowStart, rowEnd, colStart, colEnd := ranges[cur][0], ranges[cur][1], ranges[cur][2], ranges[cur][3]
freq, nodeCount := rowEnd-rowStart, colEnd-colStart
if nodeCount > 0 && freq == 2 {
belong1, belong2 := 0, 0
for i := rowStart; i < rowEnd; i++ {
if sa[i] < n1 {
belong1++
} else if sa[i] > n1 {
belong2++
}
}
if belong1 == 1 && belong2 == 1 {
minLength := colStart + 1
res = min32(res, minLength)
}
}
for _, v := range tree[cur] {
dfs(v)
}
}
dfs(0)
if res == INF {
res = -1
}
fmt.Fprintln(out, res)
}
// Fake News (hard)
// https://www.luogu.com.cn/problem/CF802I
// 给出 s，求所有 s 的本质不同子串 ss 在 s 中的出现次数平方和，重复的子串只算一次。
// 同cf123d
func cf802I() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
solve := func() {
var s string
fmt.Fscan(in, &s)
_, ranges := SuffixTree(int32(len(s)), func(i int32) int32 { return int32(s[i]) })
res := 0
for i := 1; i < len(ranges); i++ {
rowStart, rowEnd, colStart, colEnd := ranges[i][0], ranges[i][1], ranges[i][2], ranges[i][3]
freq, nodeCount := int(rowEnd-rowStart), int(colEnd-colStart)
res += (freq * freq) * nodeCount
}
fmt.Fprintln(out, res)
}
var T int
fmt.Fscan(in, &T)
for ; T > 0; T-- {
solve()
}
}
// Forbidden Indices
// https://codeforces.com/problemset/problem/873/F
// 给出一个字符串 s，一个 01 串，长度均为 n（n≤2e5）.
// !设 ss 为 s 的一个子串，求 `ss长度*不在被禁止位置结束的子串ss出现次数` 的最大值。
//
// 取反串，限制条件就变成了`不在被禁止位置开始的子串ss出现次数`, 转换成`禁止一些后缀`.
// 建立后缀树即可.
func cf873F() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int
fmt.Fscan(in, &n)
var s string
fmt.Fscan(in, &s)
var forbidden string
fmt.Fscan(in, &forbidden)
s, forbidden = reverseString(s), reverseString(forbidden)
sa, _, height := SuffixArray32(int32(len(s)), func(i int32) int32 { return int32(s[i]) })
ok := make([]bool, n) // 按照sa数组顺序的ok的后缀起点.
for i := 0; i < n; i++ {
j := sa[i]
ok[i] = forbidden[j] == '0'
}
okPreSum := make([]int, n+1)
for i := 1; i <= n; i++ {
okPreSum[i] = okPreSum[i-1]
if ok[i-1] {
okPreSum[i]++
}
}
_, ranges := SuffixTreeFrom(sa, height)
res := 0
for i := 1; i < len(ranges); i++ {
rowStart, rowEnd := ranges[i][0], ranges[i][1]
freq := okPreSum[rowEnd] - okPreSum[rowStart]
length := int(ranges[i][3])
res = max(res, freq*length)
}
fmt.Fprintln(out, res)
}
// P3181 [HAOI2016] 找相同字符
// 求两个字符的相同子串对数.两个方案不同当且仅当这两个子串中有一个位置不同。
// https://www.luogu.com.cn/problem/P3181
//
// 令s12 := s1 + "#" + s2，遍历后缀树，对每个结点统计belong即可.
func P3181() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var s1, s2 string
fmt.Fscan(in, &s1, &s2)
n1 := int32(len(s1))
s12 := s1 + "#" + s2
sa, _, height := SuffixArray32(int32(len(s12)), func(i int32) int32 { return int32(s12[i]) })
tree, ranges := SuffixTreeFrom(sa, height)
res := 0
var dfs func(cur int32)
dfs = func(cur int32) {
rowStart, rowEnd, colStart, colEnd := ranges[cur][0], ranges[cur][1], ranges[cur][2], ranges[cur][3]
freq, nodeCount := rowEnd-rowStart, colEnd-colStart
if nodeCount > 0 && freq >= 2 {
belong1, belong2 := 0, 0
for i := rowStart; i < rowEnd; i++ {
if sa[i] < n1 {
belong1++
} else if sa[i] > n1 {
belong2++
}
}
res += int(belong1) * int(belong2) * int(nodeCount)
}
for _, v := range tree[cur] {
dfs(v)
}
}
dfs(0)
fmt.Fprintln(out, res)
}
// P3804 【模板】后缀自动机（SAM）
// https://www.luogu.com.cn/problem/P3804
// 请你求出 S 的所有出现次数不为 1 的子串的出现次数乘上该子串长度的最大值
func p3804() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var s string
fmt.Fscan(in, &s)
tree, ranges := SuffixTree(int32(len(s)), func(i int32) int32 { return int32(s[i]) })
res := 0
var dfs func(cur int32)
dfs = func(cur int32) {
freq, nodeCount := ranges[cur][1]-ranges[cur][0], ranges[cur][3]-ranges[cur][2]
if nodeCount > 0 && freq > 1 {
maxLength := int(ranges[cur][3])
res = max(res, maxLength*int(freq))
}
for _, v := range tree[cur] {
dfs(v)
}
}
dfs(0)
fmt.Fprintln(out, res)
}
// P4341 [BJWC2010] 外星联络
// https://www.luogu.com.cn/problem/P4341
// 给一个字符串求所以出现次数大于 1 的子串所出现的次数。输出的顺序按对应的子串的字典序排列。
func p4341() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int
fmt.Fscan(in, &n)
var s string
fmt.Fscan(in, &s)
tree, ranges := SuffixTree(int32(len(s)), func(i int32) int32 { return int32(s[i]) })
var res []int32
var dfs func(cur int32)
dfs = func(cur int32) {
freq, nodeCount := ranges[cur][1]-ranges[cur][0], ranges[cur][3]-ranges[cur][2]
if freq > 1 {
for i := int32(0); i < nodeCount; i++ {
res = append(res, freq)
}
}
for _, v := range tree[cur] {
dfs(v)
}
}
dfs(0)
for _, v := range res {
fmt.Fprintln(out, v)
}
}
// P5341 [TJOI2019] 甲苯先生和大中锋的字符串
// https://www.luogu.com.cn/problem/P5341
// 给定字符串s, 求出现 k 次的子串中出现次数的最多的长度。如果不存在子串出现 k 次，则输出 −1 。
func p5341() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
solve := func(s string, k int32) int {
tree, ranges := SuffixTree(int32(len(s)), func(i int32) int32 { return int32(s[i]) })
lengthCounter := make([]int, len(s)+2)
add := func(min int32, max int32, val int) {
lengthCounter[min] += val
lengthCounter[max+1] -= val
}
build := func() {
for i := 1; i < len(lengthCounter); i++ {
lengthCounter[i] += lengthCounter[i-1]
}
}
var dfs func(cur int32)
dfs = func(cur int32) {
freq, nodeCount := ranges[cur][1]-ranges[cur][0], ranges[cur][3]-ranges[cur][2]
if nodeCount > 0 && freq == k {
minLength, maxLength := ranges[cur][2]+1, ranges[cur][3]
add(minLength, maxLength, 1)
}
for _, v := range tree[cur] {
dfs(v)
}
}
dfs(0)
build()
res, maxCount := -1, -1
for i, v := range lengthCounter {
if v > 0 && v >= maxCount {
maxCount = v
res = i
}
}
return res
}
var T int
fmt.Fscan(in, &T)
for ; T > 0; T-- {
var s string
var k int32
fmt.Fscan(in, &s, &k)
fmt.Fprintln(out, solve(s, k))
}
}
// TODO
// 1923. 最长公共子路径(多个结点的最长公共子串)
// https://leetcode.cn/problems/longest-common-subpath/solution/hou-zhui-shu-zu-er-fen-da-an-by-endlessc-ocar/
func longestCommonSubpath(n int, paths [][]int) int {
path32 := make([][]int32, len(paths))
for i, p := range paths {
for _, v := range p {
path32[i] = append(path32[i], int32(v))
}
}
return 0
}
// https://yukicoder.me/problems/no/2361
// 给定一个长为n的字符串s和q个询问.
// 每个询问给出一个区间[start,end), 问有多少个子串的字典序严格小于s[start:end).
//
// !1.将查询的子串 s[start:end) 表示为"起点为start的后缀的长为(end-start)的一个前缀".
// !2.离线查询，按照后缀起点将查询分组，便于后续按照字典序遍历查询.
// !3.线段树维护sa数组上的查询长度最小值, 每次将查询长度最小的查询取出，保证遍历后缀树节点时可以按照字典序处理查询.
func yukicoder2361() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n, q int32
fmt.Fscan(in, &n, &q)
var s string
fmt.Fscan(in, &s)
queries := make([][2]int32, q)
for i := range queries {
fmt.Fscan(in, &queries[i][0], &queries[i][1])
queries[i][0]--
}
sa, rank, height := SuffixArray32(n, func(i int32) int32 { return int32(s[i]) })
type pair struct{ length, qid int32 } // 长度, 询问id
queryGroups := make([][]pair, n) // 按照sa数组下标分组
for i := range queries {
start, end := queries[i][0], queries[i][1]
saIndex := rank[start]
queryGroups[saIndex] = append(queryGroups[saIndex], pair{length: end - start, qid: int32(i)})
}
for _, group := range queryGroups {
// 长度短的查询排在数组末尾，先取出
sort.Slice(group, func(i, j int) bool { return group[i].length > group[j].length })
}
seg := NewSegmentTree(int(n), func(i int) E { return E{value: INF32, index: -1} }) // !维护每个saIndex对应的查询长度最小值
updateRMQ := func(saIndex int32) {
group := queryGroups[saIndex]
if len(group) == 0 {
seg.Set(int(saIndex), E{value: INF32, index: -1})
} else {
minLength := group[len(group)-1].length
seg.Set(int(saIndex), E{value: minLength, index: saIndex})
}
}
for i := int32(0); i < n; i++ {
updateRMQ(i)
}
res := make([]int, q)
suffixTree, ranges := SuffixTreeFrom(sa, height)
smaller := 0
var dfs func(cur int32)
dfs = func(cur int32) {
rowStart, rowEnd, colStart, colEnd := int(ranges[cur][0]), int(ranges[cur][1]), int(ranges[cur][2]), int(ranges[cur][3])
freq, nodeCount := rowEnd-rowStart, colEnd-colStart
minLength, maxLength := colStart+1, colEnd
// !按照字典序取出存在于当前结点(矩形)内部的所有查询
for {
item := seg.Query(rowStart, rowEnd)
queryLength, saIndex := int(item.value), item.index
if queryLength > maxLength {
break
}
group := &queryGroups[saIndex]
qid := (*group)[len(*group)-1].qid
*group = (*group)[:len(*group)-1]
updateRMQ(saIndex)
res[qid] = smaller + freq*(queryLength-minLength) // 整个矩形区域的子串个数
}
smaller += freq * nodeCount
for _, next := range suffixTree[cur] {
dfs(next)
}
}
dfs(0)
for _, v := range res {
fmt.Fprintln(out, v)
}
}
// directTree: 后缀树, 从 0 开始编号, 0 结点为虚拟根节点.
// ranges: 每个结点对应后缀数组上的 [行1，行2，列1，列2] 矩形区域.
// !(行2-行1) 表示此startPos出现次数, (列2-列1) 表示结点包含的压缩的字符串长度(个数).
// 对应后缀sa编号: [rowStart, rowEnd)
// 对应字符串长度: [colStart+1, colEnd+1)
func SuffixTree(n int32, f func(i int32) int32) (directedTree [][]int32, ranges [][4]int32) {
sa, _, lcp := SuffixArray32(n, f)
return SuffixTreeFrom(sa, lcp)
}
// 每个节点为后缀数组上的一个矩形区间.
func SuffixTreeFrom(sa, height []int32) (directedTree [][]int32, ranges [][4]int32) {
height = height[1:]
n := int32(len(sa))
if n == 1 {
directedTree = make([][]int32, 2)
directedTree[0] = append(directedTree[0], 1)
ranges = append(ranges, [4]int32{0, 1, 0, 0})
ranges = append(ranges, [4]int32{0, 1, 0, 1})
return
}
var edges [][2]int32
ranges = append(ranges, [4]int32{0, n, 0, 0})
ct := NewCartesianTreeSimple32(height)
var dfs func(p, idx int32, h int32)
dfs = func(p, idx int32, h int32) {
left, right := ct.Range[idx][0], ct.Range[idx][1]+1
hh := height[idx]
if h < hh {
m := int32(len(ranges))
edges = append(edges, [2]int32{p, m})
p = m
ranges = append(ranges, [4]int32{left, right, h, hh})
}
if ct.leftChild[idx] == -1 {
if hh < n-sa[idx] {
edges = append(edges, [2]int32{p, int32(len(ranges))})
ranges = append(ranges, [4]int32{idx, idx + 1, hh, n - sa[idx]})
}
} else {
dfs(p, ct.leftChild[idx], hh)
}
if ct.rigthChild[idx] == -1 {
if hh < n-sa[idx+1] {
edges = append(edges, [2]int32{p, int32(len(ranges))})
ranges = append(ranges, [4]int32{idx + 1, idx + 2, hh, n - sa[idx+1]})
}
} else {
dfs(p, ct.rigthChild[idx], hh)
}
}
root := ct.Root
if height[root] > 0 {
edges = append(edges, [2]int32{0, 1})
ranges = append(ranges, [4]int32{0, n, 0, height[root]})
dfs(1, root, height[root])
} else {
dfs(0, root, 0)
}
directedTree = make([][]int32, len(ranges))
for _, e := range edges {
u, v := e[0], e[1]
directedTree[u] = append(directedTree[u], v)
}
return
}
// 给定后缀数组上的范围 [row, colStart, colEnd]，求出这个区间对应的字符串s[start:end)。
func RecoverSubstring(sa []int32, row int32, colStart, colEnd int32) (start, end int32) {
start = sa[row] + colStart
end = sa[row] + colEnd
return
}
func SuffixArray32(n int32, f func(i int32) int32) (sa, rank, height []int32) {
s := make([]byte, 0, n*4)
for i := int32(0); i < n; i++ {
v := f(i)
s = append(s, byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
}
_sa := *(*[]int32)(unsafe.Pointer(reflect.ValueOf(suffixarray.New(s)).Elem().FieldByName("sa").Field(0).UnsafeAddr()))
sa = make([]int32, 0, n)
for _, v := range _sa {
if v&3 == 0 {
sa = append(sa, v>>2)
}
}
rank = make([]int32, n)
for i := int32(0); i < n; i++ {
rank[sa[i]] = i
}
height = make([]int32, n)
h := int32(0)
for i := int32(0); i < n; i++ {
rk := rank[i]
if h > 0 {
h--
}
if rk > 0 {
for j := sa[rk-1]; i+h < n && j+h < n && f(i+h) == f(j+h); h++ {
}
}
height[rk] = h
}
return
}
type CartesianTreeSimple32 struct {
// ![left, right) 每个元素作为最大/最小值时的左右边界.
// 左侧为严格扩展, 右侧为非严格扩展.
// 例如: [2, 1, 1, 5] => [[0 1] [0 4] [2 4] [3 4]]
Range [][2]int32
Root int32
n int32
nums []int32
leftChild, rigthChild, parent []int32
}
// min
func NewCartesianTreeSimple32(nums []int32) *CartesianTreeSimple32 {
res := &CartesianTreeSimple32{}
n := int32(len(nums))
Range := make([][2]int32, n)
lch := make([]int32, n)
rch := make([]int32, n)
par := make([]int32, n)
for i := int32(0); i < n; i++ {
Range[i] = [2]int32{-1, -1}
lch[i] = -1
rch[i] = -1
par[i] = -1
}
res.n = n
res.nums = nums
res.Range = Range
res.leftChild = lch
res.rigthChild = rch
res.parent = par
if n == 1 {
res.Range[0] = [2]int32{0, 1}
return res
}
less := func(i, j int32) bool {
return (nums[i] < nums[j]) || (nums[i] == nums[j] && i < j)
}
stack := make([]int32, 0)
for i := int32(0); i < n; i++ {
for len(stack) > 0 && less(i, stack[len(stack)-1]) {
res.leftChild[i] = stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
res.Range[i][0] = 0
if len(stack) > 0 {
res.Range[i][0] = stack[len(stack)-1] + 1
}
stack = append(stack, i)
}
stack = stack[:0]
for i := n - 1; i >= 0; i-- {
for len(stack) > 0 && less(i, stack[len(stack)-1]) {
res.rigthChild[i] = stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
res.Range[i][1] = n
if len(stack) > 0 {
res.Range[i][1] = stack[len(stack)-1]
}
stack = append(stack, i)
}
for i := int32(0); i < n; i++ {
if res.leftChild[i] != -1 {
res.parent[res.leftChild[i]] = i
}
if res.rigthChild[i] != -1 {
res.parent[res.rigthChild[i]] = i
}
}
for i := int32(0); i < n; i++ {
if res.parent[i] == -1 {
res.Root = i
}
}
return res
}
// PointSetRangeMinIndex
const INF32 int32 = 1e9 + 10
type E = struct{ value, index int32 }
func (*SegmentTree) e() E {
return E{value: INF32, index: -1}
}
func (*SegmentTree) op(a, b E) E {
if a.value < b.value {
return a
}
if a.value > b.value {
return b
}
if a.index < b.index {
return a
}
return b
}
type SegmentTree struct {
n, size int
seg []E
}
func NewSegmentTree(n int, f func(int) E) *SegmentTree {
res := &SegmentTree{}
size := 1
for size < n {
size <<= 1
}
seg := make([]E, size<<1)
for i := range seg {
seg[i] = res.e()
}
for i := 0; i < n; i++ {
seg[i+size] = f(i)
}
for i := size - 1; i > 0; i-- {
seg[i] = res.op(seg[i<<1], seg[i<<1|1])
}
res.n = n
res.size = size
res.seg = seg
return res
}
func NewSegmentTreeFrom(leaves []E) *SegmentTree {
res := &SegmentTree{}
n := len(leaves)
size := 1
for size < n {
size <<= 1
}
seg := make([]E, size<<1)
for i := range seg {
seg[i] = res.e()
}
for i := 0; i < n; i++ {
seg[i+size] = leaves[i]
}
for i := size - 1; i > 0; i-- {
seg[i] = res.op(seg[i<<1], seg[i<<1|1])
}
res.n = n
res.size = size
res.seg = seg
return res
}
func (st *SegmentTree) Get(index int) E {
if index < 0 || index >= st.n {
return st.e()
}
return st.seg[index+st.size]
}
func (st *SegmentTree) Set(index int, value E) {
if index < 0 || index >= st.n {
return
}
index += st.size
st.seg[index] = value
for index >>= 1; index > 0; index >>= 1 {
st.seg[index] = st.op(st.seg[index<<1], st.seg[index<<1|1])
}
}
func (st *SegmentTree) Update(index int, value E) {
if index < 0 || index >= st.n {
return
}
index += st.size
st.seg[index] = st.op(st.seg[index], value)
for index >>= 1; index > 0; index >>= 1 {
st.seg[index] = st.op(st.seg[index<<1], st.seg[index<<1|1])
}
}
// [start, end)
func (st *SegmentTree) Query(start, end int) E {
if start < 0 {
start = 0
}
if end > st.n {
end = st.n
}
if start >= end {
return st.e()
}
leftRes, rightRes := st.e(), st.e()
start += st.size
end += st.size
for start < end {
if start&1 == 1 {
leftRes = st.op(leftRes, st.seg[start])
start++
}
if end&1 == 1 {
end--
rightRes = st.op(st.seg[end], rightRes)
}
start >>= 1
end >>= 1
}
return st.op(leftRes, rightRes)
}
func (st *SegmentTree) QueryAll() E { return st.seg[1] }
func (st *SegmentTree) GetAll() []E {
res := make([]E, st.n)
copy(res, st.seg[st.size:st.size+st.n])
return res
}
// 二分查询最大的 right 使得切片 [left:right] 内的值满足 predicate
func (st *SegmentTree) MaxRight(left int, predicate func(E) bool) int {
if left == st.n {
return st.n
}
left += st.size
res := st.e()
for {
for left&1 == 0 {
left >>= 1
}
if !predicate(st.op(res, st.seg[left])) {
for left < st.size {
left <<= 1
if tmp := st.op(res, st.seg[left]); predicate(tmp) {
res = tmp
left++
}
}
return left - st.size
}
res = st.op(res, st.seg[left])
left++
if (left & -left) == left {
break
}
}
return st.n
}
// 二分查询最小的 left 使得切片 [left:right] 内的值满足 predicate
func (st *SegmentTree) MinLeft(right int, predicate func(E) bool) int {
if right == 0 {
return 0
}
right += st.size
res := st.e()
for {
right--
for right > 1 && right&1 == 1 {
right >>= 1
}
if !predicate(st.op(st.seg[right], res)) {
for right < st.size {
right = right<<1 | 1
if tmp := st.op(st.seg[right], res); predicate(tmp) {
res = tmp
right--
}
}
return right + 1 - st.size
}
res = st.op(st.seg[right], res)
if right&-right == right {
break
}
}
return 0
}
func reverseString(s string) string {
n := len(s)
runes := make([]rune, n)
for _, r := range s {
n--
runes[n] = r
}
return string(runes)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func max32(a, b int32) int32 {
if a > b {
return a
}
return b
}
func min32(a, b int32) int32 {
if a < b {
return a
}
return b
}