题解 | #游游的好串#

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int n = s.length();
        long res = 0;
        // 维护一个栈，记录字符串中1出现的位置，当有0时则弹出1
        Deque<Integer> st = new ArrayDeque<>();
        // ans[i]表示以i为开头最长好串的长度
        int[] ans = new int[n];
        for(int i = n - 1; i >= 0; i--) {
            if(s.charAt(i) == '1') {
                st.push(i);
            } else {
                // 一个好串它的所有前缀(下标0开始的子串)也都是好串
                ans[i] = st.isEmpty() ? n - i : st.pop() - i;
                res += ans[i];
            }
        }
        System.out.println(res);
    }
}