HJ134 1or0

• 题目
• 题解(7)
• 讨论(8)
• 排行

较难 通过率：17.36% 时间限制：1秒 空间限制：1024M

知识点动态规划

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

定义由 nn 个字符组成的二进制字符串 s1s2⋯sns1​s2​⋯sn​ 的“自审值”为：s1or⁡s2or⁡⋯or⁡sns1​ors2​or⋯orsn​。
现在，对于给定的字符串，你需要独立处理 qq 次询问。每一次询问给定一个区间 [l,r][l,r]，求解区间内全部连续子串的“自审值”之和。

其中，or⁡or 表示按位或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。
子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

输入描述：

第一行输入一个整数 n(1≦n≦2×105)n(1≦n≦2×105) 代表字符串的长度。
第二行输入一个长度为 nn、仅由 ‘0’‘0’ 和 ‘1’‘1’ 两个字符组成的字符串 ss，代表给定的字符串。下标从 11 开始。

第三行输入一个整数 q(1≦q≦2×105)q(1≦q≦2×105) 代表询问次数。
此后 qq 行，每行输入两个整数 l,r(1≦l≦r≦n)l,r(1≦l≦r≦n) 代表询问的区间。

输出描述：

对于每一次询问，新起一行。输出一个整数，代表区间内全部连续子串的“自审值”之和。

示例1

输入：

5 10110 2 3 5 1 1

复制输出：

5 1

复制说明：

对于第一次询问，拆分出全部子区间： ∙ ∙区间 [3,3][3,3] 的“自审值”为 11； ∙ ∙区间 [3,4][3,4] 的“自审值”为 1or⁡1=11or1=1； ∙ ∙区间 [3,5][3,5] 的“自审值”为 1or⁡1or⁡0=11or1or0=1； ∙ ∙区间 [4,4][4,4] 的“自审值”为 11； ∙ ∙区间 [4,5][4,5] 的“自审值”为 1or⁡0=11or0=1； ∙ ∙区间 [5,5][5,5] 的“自审值”为 00； 综上所述，“自审值”之和为 1+1+1+1+1+0=51+1+1+1+1+0=5。

#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; }