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