E1. Cats on the Upgrade (easy version)
题意
给定一个长度为\(n\)的括号串,\(q\)次询问,问区间\([l,r]\)所表示的子串中有多少个合法的括号子串,保证区间\([l,r]\)所表示的子串是合法括号子串。
分析
认为空串也算作广义的括号串。记广义括号串为RBS
,则所有的括号串(不含空串)都有形如(RBS)(RBS)...(RBS)
的形式。不妨设计状态dp[i]
,表示以第\(i\)个字符为结尾,连续的(RBS)
的个数,特殊地,dp[0] = 0
。那么对于所有前缀这个问题就已经解决了,只需要一个前缀和就可以多次询问,于是可以定义sum[i] = dp[1] + dp[2] + ... + dp[i]
,特殊地,sum[0] = 0
。
若询问的是区间\([l,r]\),sum[r] - sum[l-1]
计算了以区间\([l,r]\)中的所有点为结尾的贡献,显然这样计算很可能会多算。由于题目保证区间\([l,r]\)所表示的子串是合法括号子串,对于\([l,r]\)中的每一个点\(i\)来说,只有当第\(i\)个字符是右括号,且以其为结尾的连续的(RBS)
中能够包含第\(l\)个字符(其一定是左括号),才会多算,且对于每个满足上述条件的点来说一定会多算dp[l-1]
的贡献。所以就需要计算\([l,r]\)中有多少个满足上述条件的点,由于题目保证区间\([l,r]\)所表示的子串是合法括号子串,显然以\(r\)为结尾的连续(RBS)
一定包含了所有满足条件的右括号,且一定不包含\([l,r]\)中不满足条件的右括号,一个(RBS)
严格对应了一个满足条件的右括号,所以\([l,r]\)中有dp[r] - dp[l-1]
个满足条件的右括号。
故而最终结果就是sum[r] - sum[l-1] - dp[l-1] * (dp[r] - dp[l-1])
代码
#include <cstdio>
const int maxn = 3e5 + 10;
typedef long long Lint;
int n, q, st[maxn];
Lint dp[maxn], sum[maxn];
int tot;
char s[maxn];
int main() {
scanf("%d%d", &n, &q);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) {
if (s[i] == '(') {
st[tot++] = i;
} else if (tot) {
dp[i] = dp[st[tot - 1] - 1] + 1;
--tot;
}
sum[i] = dp[i] + sum[i - 1];
}
while (q--) {
int l, r;
scanf("%*d%d%d", &l, &r);
printf("%lld\n", sum[r] - sum[l - 1] - dp[l - 1] * (dp[r] - dp[l - 1]));
}
return 0;
}