注意，下文默认下标从 0 开始，且下文所提及的 i 表示现在枚举到的下标，qzh 代表前缀和数组。

暴力 我们可以先想一下暴力的解法。假设我们现在是要让 l 到 r 这个区间内 1 的个数大于 0。那么我们先枚举 l，用两个变量 cnt1 和 cnt0 分别存储当前 1 和 0 的个数，随后枚举 r，对于当前 cnt1>cnt0，就将答案加 1。这种做法的时间复杂度是 $O(n^2 )$，期望得分 20 分。

前缀和加哈希表优化 接下来我们考虑给这个字符串做前缀和，将 1 的贡献设为 1，0 的贡献设为 −1。那么，当前缀和的值大于 0 的时候，就说明 0 到 i 这段区间内 1 的个数就大于 0 的个数。 但是对于 l 和 r 呢？l 不一定为 0 啊！这有咋办呢？我们发现如果 $qzh_r​ −qzh_{l−1}$ ​ 如果大于 0 其实就代表 l 到 r 这段区间内 1 的个数大于 0 的个数。那么对于 r，我们只需要求满足 $qzh_l​ <qzh_r$​ 的 l 的个数。
现在我们用一个哈希表 mp，mp k​ 表示满足 $qzh_ j =k∧j<i$ 的 j 的个数，再来个变量 cnt，表示对于当前的前缀和前面有多少前缀和小于它。对于当前位置是 1，将 cnt 加上 $mp_{sum}​$ ，其中 sum 表示当前的前缀和，对于当前位置是 0，将 cnt 减去 $mp_{sum−1}$​ ，最后每次都将 ans 加上 cnt 即可。
这里再稍微解释一下上面这样做的原因。对于当前位置是 1 的情况，我们 sum 会加上 1，那么当前的 sum 就满足条件了。同样的，当前位置是 0，sum 就会减去 1，那么当前的 sum−1 就不满足条件了。 需要将 $mp_0$ ​ 初始化为 1，同学们可以想想为什么。 其实这种做法已经接近正解了，我整出了个 90 分。。。 这一部分没理解的同学请落实到位，很重要！！！
90 分代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
unordered_map<ll,ll>mp;
string s;
ll ans,sum,cnt,n;
int main(){
    cin>>n>>s;
    mp[0]=1;
    for(int i=0;i<n;i++){
        if(s[i]=='1') cnt+=mp[sum],sum++;
        else cnt-=mp[sum-1],sum--;
        mp[sum]++; ans+=cnt;
    }
    cout<<ans<<'\n';
    return 0;
}

正解 这里会超时的原因是被卡常了哈希表很浪费时间。我们把哈希表改成数组就好了。。。 这里将哈希表改成数组的原理很简单，因为 sum 再怎么减都不会小于 n，我们只需将每一位都右移 n 位即可，这样就能保证不会超到负数，数组开两倍大就好了。 正解时间复杂度 O(n)，跑得飞快。