LC 3234. 统计 1 显著的字符串的数量

https://leetcode.cn/problems/count-the-number-of-substrings-with-dominant-ones/description/

这题突破口还是平方这个地方。所以一般来说如果N~=10^4这个范围上，并且有平方的话，那么复杂度可能就是O(n sqrt(n)).

这题实现思路上是，枚举所有出现0的位置点，然后0出现的次数不会超过O(sqrt(n))个，所以复杂度就是在O(n sqrt(n))上。

枚举0的位置点之后，假设 

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        pos = [n] * (n + 1)
        for i in reversed(range(n)):
            pos[i] = i if s[i] == '0' else pos[i + 1]

        ans = 0
        for l in range(n):
            zero = 0
            r0 = pos[l]
            # [l..r0][r0+1..r1)
            # s[r0/r1] == '0'
            ans += (r0 - l)

            while r0 < n:
                zero += 1
                if zero * zero > (n - l): break
                r1 = pos[r0 + 1]
                a = (r0 - l + 1) - zero
                b = max(zero * zero - a, 0)
                if b > (n - r0): break
                r = max(r1 - r0 - b, 0)
                ans += r
                r0 = r1
        return ans