题面

游游的好串
游游有一个只包含'0'和'1'的字符串，他想知道这个字符串有多少个好子串？

一个字符串如果是"好串"，那么该字符串的所有前缀，'0'的数量严格大于'1'的数量。

输入

输入一个只包含'0'和'1'的字符串，长度不超过100000。

输出

输出一个整数，代表答案。

示例

输入例子：

100

输出例子：

3

例子说明：
子区间 [2, 2], [2, 3], [3, 3] 组成的子串都是一个好串。

输入例子：

10010

输出例子：

6

例子说明：
子区间 [2, 2], [3, 3], [2, 3], [2, 4], [2, 5], [5, 5] 组成的子串是一个好串。

核心思想

滑动窗口
首先要明确的一点时窗口滑动的过程本身就是前缀
那么窗口两端 l，r 表示 从 l 开始，以 r 结尾的所有子串满足要求的有多少个
这一步操作就是选择了子串 [l,r] [l+1,r]....[r,r]
以 10010 为例

当窗口来到 l = 2, r = 4 时（下标从1开始）窗口串为 001
我们执行 res += (r - l + 1); 这一计算的意义是什么？
我们认为 001, 01, 1 这样的字串都满足要求 但事实上 01, 1 是需要剔除的
分析后可以发现是因为有1的存在
分为两种情况

1. 以 1 开头的字串， 数量为窗口内 1 的个数
2. 第二种就是上面例子中 01 这样的 前面0的个数太少 这样的有多少个？同样是 1 的个数

我们换一个例子 0010101,窗口会来到 l = 1, r = 7, cnt1 = 3（窗口内1的个数）
010101, 10101
0101, 101
01, 1
这些都是不满足的 也就是1的个数乘2

代码

import java.util.*;

class Main {
    static final int MAXN = (int) (1e5 + 10);
    static char[] chs = new char[MAXN];
    static long res = 0;
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int n = s.length();
        for(int i = 1; i <= n; i++){
            chs[i] = s.charAt(i - 1);
        }
        int cnt1 = 0, cnt0 = 0;
        for(int l = 1, r = 1; r <= n; r++){
            if(chs[r] == '0')
                cnt0++;
            else{
                cnt1++;
            }

            while(cnt1 >= cnt0 && l <= r){
                if(chs[l] == '0')
                    cnt0--;
                else
                    cnt1--;
                l++;
            }
            res += (r - l + 1);
            res -= 2L * cnt1;
        }
        System.out.println(res);
    }
}