Readme

3234.Count-the-Number-of-Substrings-With-Dominant-Ones

对于substring，我们第一个想法是考虑前缀之差。假设以i为结尾的前缀里有x个1和y个0，那么我们希望找一个已有的前缀位置j（其包含p个1和q个0），需要满足(x-p)>=(y-q)^2. 由于这其中包含了平方关系，很难构造hash找出符合条件的j。

这是我们再审查这个平方关系。一般情况下，这意味着substring里的1要比0多很多。比如说有10个一，那么就需要有100个零。考虑到s的总长度也不过是4e4，这就意味着其实我们寻找的字符串里最多也就200个零，再配上40000个一就到达极限了。

所以此时我们的方案几乎就呼之欲出了，那就是穷举包含零的个数为1到200的substring。我们遍历长度m=1,...,200，对于每个固定的m，通过一遍单调的双指针移动就可以把所有包含零的个数是m的滑窗都找出来。时间复杂度是o(200n)，符合题意。

假设找到一段滑窗，里面包含了m个零，那么该如何计数以它为基础的符合条件的substring呢？一种想法是，假设确定了最外边的两个0的位置i和j，那么我们可以自由调配i左边的1的个数、以及j右边的1的个数，但要使得区间内的0（个数已经固定）与1的个数符合条件。这样的方法比较复杂。

其实有一种更简单的做法，那么穷举substring的左边界i（不管是0还是1），通过上述的滑窗准则，找到对应右边界的j使得[i:j]恰好有m个0，另外有t个1. 那么我们可以知道，至少还需要m*m-t个1，这就需要从s[j]右边的若干个连续的1里面取。假设s[j]右边有连续k个1，那么超过m*m-t的部分我们可以自由选择，故有k-(m*m-t)+1种合法的substring右边界。

另外，对于m=0的特殊情况我们要单独处理。即substring里只含有1不含有0. 那么任意以1为左边界的substring，它的右边界可以包含任意数目的连续的1.