如何在O(nlogn)时间内统计二进制字符串的稠密子串数量

稠密子串（Dense sub-string）：子串中1的数量大于0的数量

C++暴力解法 #

#include <iostream>
#include <string>

using namespace std;

int bin_dense_count_bruteforce(string s) {
    int n = s.size();
    int ans = 0;

    for(int i=0; i<=n-1; i++) {
        int statusNow = 0;
        
        for(int j=i; j<=n-1; j++) {
            if(s[j] == '1')
                statusNow++;
            else
                statusNow--;

            if(statusNow>0)
                ans++;
        }
    }

    return ans;
}

int main() {
    string s = "11000101";

    cout<<bin_dense_count_bruteforce(s)<<endl;
    // 7
    // i, j substring
    // 0, 0 1
    // 0, 1 11
    // 0, 2 110
    // 1, 1 1
    // 5, 5 1
    // 5, 7 101
    // 7, 7 1

    return 0;
}

我曾尝试基于unordered_map的前缀和类方法，也通过网络及ChatGPT、Claude等工具查找方案，但均未成功，现寻求O(nlogn)时间复杂度的解法。

内容的提问来源于stack exchange，提问作者Rajan