题解 | 1or0（前缀和）

#牛客春招刷题训练营# + 链接

容易发现，只有全0的子串“自审值”才是0，因此计算全0子串的个数（res），从总数中减去

顺序扫描的同时维护左侧最近的1的位置，扫描到0时作为右端点计算

处理询问时，当第l位为0时res可能会包含左端点在区间外面的子串，需要特殊处理减去

单次询问复杂度O(1)

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MAXN=200010;
char s[MAXN];
int prep[MAXN], sufp[MAXN];
ll presy[MAXN];

int main() {
    int n, q;
    scanf("%d", &n);
    scanf("%s", s+1);
    for (int i=1;i<=n;i++) {
        prep[i] = prep[i-1];
        presy[i] = presy[i-1];
        if (s[i] == '1') {
            prep[i] = i;
        } else {
            presy[i] += i-prep[i];
        }
    }
    sufp[n+1] = n+1;
    for (int i=n;i;i--) {
        sufp[i] = sufp[i+1];
        if (s[i+1]=='1') {
            sufp[i] = i+1;
        }
    }
    scanf("%d", &q);
    while (q--) {
        int l,r;
        scanf("%d%d",&l,&r);
        ll tot = 1LL * (r-l+2) * (r-l+1) / 2;
        ll res = presy[r]-presy[l-1];
        if (s[l]=='0') {
            int y = sufp[l]-1;
            if (y>r) y=r;
            res -= 1LL * (l-prep[l]-1) * (y-l+1);
        }
        printf("%lld\n", tot-res);
    }
    return 0;
}