题解 | #1or0#

0子串

本题特点：基础解法并不难，但是对性能要求高。具体思路：

1. 用总的子串数 - 0子串数，就是‘区间内全部连续子串的“自审值”之和’。
2. 而0子串数可以使用前缀和的思路来快速计算出区间内的0子串数。
3. 但是如果区间是以0开头的，则pre[j] - pre[i-1]的值中就会多包涵一些从i的左边开头在[i,j]区间内（包扩两个边界值）结尾的0子串，要减去这一部分。

具体代码如下：

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner fs = new Scanner(System.in);
        StringBuilder out = new StringBuilder();

        int n = fs.nextInt();
        String ss = fs.next();

        // prep[i]: 最靠近 i（<=i）的 '1' 的位置，若没有则为 0
        int[] prep = new int[n];
        prep[0] = (ss.charAt(0) == '1' ? 0 : -1);
        // preZeroSubStr[i]: i位置之前时（包含i）有多少个以0结尾的子串
        long[] preZeroSubStr = new long[n];
        preZeroSubStr[0] = (ss.charAt(0) == '1' ? 0 : 1);
        for (int i = 1; i < n; i++) {
            preZeroSubStr[i] = preZeroSubStr[i - 1]; //顺延吧
            if (ss.charAt(i) == '1') {
                prep[i] = i;
            } else {
                prep[i] = prep[i - 1];
                // s[i] == '0' , 有（i-prep[i]）个以s[i]='0'为结尾的0子串。
                preZeroSubStr[i] += (i - prep[i]);
            }
        }

        // sufp[i]: i 之后最近的 '1' 的位置（包括i）
        int[] sufp = new int[n];
        sufp[n - 1] = n;
        for (int i = n - 2; i >= 0; i--) {
            sufp[i] = sufp[i + 1];
            if (ss.charAt(i) == '1') {
                sufp[i] = i;
            }
        }

        int q = fs.nextInt();
        // 注意不用预先计算所有的（i，j）因为大概率查询不会重复的，所以需要实时计算。
        while (q-- > 0) {
            int l = fs.nextInt();
            int r = fs.nextInt();
            int ll = l - 1;
            int rr = r - 1;

            // 总的子串 in [l, r]: len*(len+1)/2
            long len = r - l + 1;
            long tot = len * (len + 1L) / 2L;
            // 0子串
            long res = preZeroSubStr[rr] - (ll > 0 ? preZeroSubStr[ll - 1] : 0);

            // 如果 s[ll] 是 '0'，说明可能存在从ll的左侧开始但在 [ll..rr] 结尾的全零子串，需要扣除
            if (ss.charAt(ll) == '0') {
                // y是ll右边的最近的1的下标
                int y = sufp[ll] - 1; // 需要减去1，表示最后一个0的位置
                if (y > rr) y = rr;
                long k = ll - prep[ll] - 1; // 这里的1表示不包含ll位置的0
                if (k > 0 && y >= ll) {
                    // ll的左边有k个0，ll的右边（包括ll）有（y-ll+1）哥0，两者相乘，就是多计算的0子串
                    res -= k * (y - ll + 1L);
                }
            }

            long ans = tot - res;
            out.append(ans).append('\n');
        }

        System.out.print(out);
    }
}