#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; // 程序结束
}
详细注释说明
- 头文件和命名空间:#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 ) 的所有子串的“自审值”之和。
- 输入字符串:scanf("%d", &n);:读取字符串长度。scanf("%s", s + 1);:读取字符串,从 s[1] 开始存储,方便处理下标。
- 预处理 prep 和 presy:遍历字符串,更新 prep[i] 和 presy[i]。如果当前字符是 '1',更新 prep[i] 为当前位置 ( i )。如果当前字符是 '0',计算从 prep[i] 到当前位置的子串数量,并累加到 presy[i]。
- 预处理 sufp:从字符串末尾向前遍历,更新 sufp[i]。如果下一个字符是 '1',更新 sufp[i] 为当前位置 ( i+1 )。
- 处理询问:读取每个询问的区间 ([l, r])。计算区间内所有可能的子串数量 total_substrings。计算区间内所有子串的“自审值”之和 invalid_substrings。如果 s[l] == '0',减去那些不包含 '1' 的子串的贡献。输出最终结果 total_substrings - invalid_substrings。