<p>You are given a binary string <code>s</code>.</p>

<p>Return the number of <span data-keyword="substring-nonempty">substrings</span> with <strong>dominant</strong> ones.</p>

<p>A string has <strong>dominant</strong> ones if the number of ones in the string is <strong>greater than or equal to</strong> the <strong>square</strong> of the number of zeros in the string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;00011&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<p>The substrings with dominant ones are shown in the table below.</p>
</div>

<table>
	<thead>
		<tr>
			<th>i</th>
			<th>j</th>
			<th>s[i..j]</th>
			<th>Number of Zeros</th>
			<th>Number of Ones</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>3</td>
			<td>3</td>
			<td>1</td>
			<td>0</td>
			<td>1</td>
		</tr>
		<tr>
			<td>4</td>
			<td>4</td>
			<td>1</td>
			<td>0</td>
			<td>1</td>
		</tr>
		<tr>
			<td>2</td>
			<td>3</td>
			<td>01</td>
			<td>1</td>
			<td>1</td>
		</tr>
		<tr>
			<td>3</td>
			<td>4</td>
			<td>11</td>
			<td>0</td>
			<td>2</td>
		</tr>
		<tr>
			<td>2</td>
			<td>4</td>
			<td>011</td>
			<td>1</td>
			<td>2</td>
		</tr>
	</tbody>
</table>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;101101&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">16</span></p>

<p><strong>Explanation:</strong></p>

<p>The substrings with <strong>non-dominant</strong> ones are shown in the table below.</p>

<p>Since there are 21 substrings total and 5 of them have non-dominant ones, it follows that there are 16 substrings with dominant ones.</p>
</div>

<table>
	<thead>
		<tr>
			<th>i</th>
			<th>j</th>
			<th>s[i..j]</th>
			<th>Number of Zeros</th>
			<th>Number of Ones</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>1</td>
			<td>1</td>
			<td>0</td>
			<td>1</td>
			<td>0</td>
		</tr>
		<tr>
			<td>4</td>
			<td>4</td>
			<td>0</td>
			<td>1</td>
			<td>0</td>
		</tr>
		<tr>
			<td>1</td>
			<td>4</td>
			<td>0110</td>
			<td>2</td>
			<td>2</td>
		</tr>
		<tr>
			<td>0</td>
			<td>4</td>
			<td>10110</td>
			<td>2</td>
			<td>3</td>
		</tr>
		<tr>
			<td>1</td>
			<td>5</td>
			<td>01101</td>
			<td>2</td>
			<td>3</td>
		</tr>
	</tbody>
</table>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 4 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists only of characters <code>&#39;0&#39;</code> and <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        # o = x[r] - x[l-1]
        # z = L - o
        # o >= z*z

        # z = b - a
        # o = L - (b - a)
        # o >= z^2
        # L - (b - a) >= b^2 - 2 a b + a^2
        # L >= b^2 - 2 a b + a^2
        # >= b(b + 1) + a(a-1) - 2 a b
        # r = 0
        # for i in range(n):
        #     o = 0
        #     z = 0
        #     for j in range(i, n):
        #         if s[j] == '1': o += 1
        #         else: z += 1
        #         if o >= z * z: r += 1

        # stupid idea: maintain substrings with Z zeroes for all Z
        s = [int(x) for x in s]
        S = [0] * (n + 1)
        for i in range(n):
            S[i] += S[i - 1] + s[i]
        res = 0
        changes = [n]
        for i in range(n)[::-1]:
            cz = 1 - s[i]
            left = i
            s0 = S[i - 1]
            for k in range(len(changes))[::-1]:
                right = changes[k]
                if cz * cz > (n - i + 1): break
                min_ones = S[left] - s0
                max_ones = S[right - 1] - s0
                res += max(0, max_ones - max(cz * cz, min_ones) + 1)
                if right == n: break
                cz += 1 - s[right]
                left = right
            if i + 1 == n or s[i] != s[i + 1] or s[i] == 0:
                changes.append(i)
        return res

        # res = 0
        # for z in range(int(n**(1/2)+1e-5)+1):
        #     print(f"{z=}")
        #     il = 0
        #     ir = 0
        #     cz, co = 0, 0
        #     cor = 0
        #     for j in range(n):
        #         x = int(s[il] == '1')
        #         if x:
        #             co += 1
        #             cor += 1
        #         else: cz += 1
        #         while cz > z:
        #             y = int(s[il] == '1')
        #             if y: co -= 1
        #             else: cz -= 1
        #             il += 1
        #         print(z, j, (cz, z), (il, ir))
        #         if il >= ir:
        #             ir, cor = il, co
        #         if cz == z and il <= j:
        #             while cor - 1 >= z * z and s[ir] == '1':
        #                 cor -= 1
        #                 ir += 1
        #             if cor >= z * z:
        #                 res += max(0, min(ir, j) - il + 1)
        #                 print("!", z, il, ir, j, (cz, co, cor), res)
        return res
20200