题目链接：3234-统计 1 显著的字符串的数量

观察：1 显著子串 至多有 ⌊n⌋ (<= 200) 个 0

使用队列，只保存 r 及其左侧的 O($\sqrt{n}$) 个 0 的下标，可以把空间复杂度优化到 O($\sqrt{n}$)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func numberOfSubstrings(s string) (ans int) {
	pos := []int{-1}
	tot := 0
	for r, ch := range s {
		if ch == '0' {
			pos = append(pos, r)
		} else {
			tot++
			ans += r - pos[len(pos)-1] // 不含 0 的子串个数
		}
		m := len(pos)
		for i := m - 1; i > 0 && (m-i)*(m-i) <= tot; i-- {
			p, q := pos[i-1], pos[i]
			c0 := m - i
			c1 := r - q + 1 - c0
			ans += max(q-max(c0*c0-c1, 0)-p, 0)
		}
	}
	return
}