题解 | 1or0

#include <bits/stdc++.h> // 包含常用的头文件，方便使用标准库功能
using namespace std;     // 使用标准命名空间，避免频繁使用 std:: 前缀

using ll = long long;     // 定义长整型的别名，便于代码简洁
const int MAXN = 200010;  // 定义最大字符串长度的常量

char s[MAXN];             // 用于存储输入的二进制字符串
int prep[MAXN];           // prep[i] 表示从字符串开头到位置 i 的最近一个 '1' 的位置
int sufp[MAXN];           // sufp[i] 表示从位置 i 到字符串末尾的最近一个 '1' 的位置
ll presy[MAXN];           // presy[i] 表示从字符串开头到位置 i 的所有子串的“自审值”之和

int main() {
    int n, q;             // n 表示字符串长度，q 表示询问次数
    scanf("%d", &n);      // 读取字符串长度
    scanf("%s", s + 1);   // 读取字符串，从 s[1] 开始存储，方便处理下标

    // 预处理 prep 和 presy 数组
    for (int i = 1; i <= n; i++) {
        prep[i] = prep[i - 1]; // 初始化 prep[i] 为前一个位置的值
        presy[i] = presy[i - 1]; // 初始化 presy[i] 为前一个位置的值
        if (s[i] == '1') { // 如果当前字符是 '1'
            prep[i] = i; // 更新 prep[i] 为当前位置 i
        } else {
            presy[i] += i - prep[i]; // 如果当前字符是 '0'，计算从 prep[i] 到当前位置的子串数量
        }
    }

    // 预处理 sufp 数组
    sufp[n + 1] = n + 1; // 初始化 sufp[n+1] 为 n+1，表示字符串末尾之后的位置
    for (int i = n; i >= 1; i--) { // 从字符串末尾向前遍历
        sufp[i] = sufp[i + 1]; // 初始化 sufp[i] 为下一个位置的值
        if (s[i + 1] == '1') { // 如果下一个字符是 '1'
            sufp[i] = i + 1; // 更新 sufp[i] 为当前位置 i+1
        }
    }

    scanf("%d", &q); // 读取询问次数
    while (q--) { // 处理每个询问
        int l, r; // l 和 r 表示询问区间的左右端点
        scanf("%d%d", &l, &r); // 读取询问区间

        // 计算区间 [l, r] 内所有可能的子串数量
        ll total_substrings = 1LL * (r - l + 2) * (r - l + 1) / 2;

        // 计算区间 [l, r] 内所有子串的“自审值”之和
        ll invalid_substrings = presy[r] - presy[l - 1];

        // 如果 s[l] == '0'，减去那些不包含 '1' 的子串的贡献
        if (s[l] == '0') {
            int first_one_pos = sufp[l] - 1; // 找到从 l 开始的第一个 '1' 的位置
            if (first_one_pos > r) first_one_pos = r; // 如果第一个 '1' 的位置超过 r，取 r
            invalid_substrings -= 1LL * (l - prep[l] - 1) * (first_one_pos - l + 1); // 减去不包含 '1' 的子串数量
        }

        // 输出结果
        printf("%lld\n", total_substrings - invalid_substrings);
    }

    return 0; // 程序结束
}

详细注释说明

1. 头文件和命名空间：#include <bits/stdc++.h>：包含常用的头文件，方便使用标准库功能。using namespace std;：使用标准命名空间，避免频繁使用 std:: 前缀。
2. 数据结构定义：using ll = long long;：定义长整型的别名，便于代码简洁。const int MAXN = 200010;：定义最大字符串长度的常量。char s[MAXN];：用于存储输入的二进制字符串。int prep[MAXN];：prep[i] 表示从字符串开头到位置 ( i ) 的最近一个 '1' 的位置。int sufp[MAXN];：sufp[i] 表示从位置 ( i ) 到字符串末尾的最近一个 '1' 的位置。ll presy[MAXN];：presy[i] 表示从字符串开头到位置 ( i ) 的所有子串的“自审值”之和。
3. 输入字符串：scanf("%d", &n);：读取字符串长度。scanf("%s", s + 1);：读取字符串，从 s[1] 开始存储，方便处理下标。
4. 预处理 prep 和 presy：遍历字符串，更新 prep[i] 和 presy[i]。如果当前字符是 '1'，更新 prep[i] 为当前位置 ( i )。如果当前字符是 '0'，计算从 prep[i] 到当前位置的子串数量，并累加到 presy[i]。
5. 预处理 sufp：从字符串末尾向前遍历，更新 sufp[i]。如果下一个字符是 '1'，更新 sufp[i] 为当前位置 ( i+1 )。
6. 处理询问：读取每个询问的区间 ([l, r])。计算区间内所有可能的子串数量 total_substrings。计算区间内所有子串的“自审值”之和 invalid_substrings。如果 s[l] == '0'，减去那些不包含 '1' 的子串的贡献。输出最终结果 total_substrings - invalid_substrings。