首页 > 其他分享 >D. Invertible Bracket Sequences

D. Invertible Bracket Sequences

时间:2024-05-31 15:56:36浏览次数:23  
标签:Invertible sequence int leq Bracket 端点 Sequences regular bracket

D. Invertible Bracket Sequences

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example:

  • bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");
  • bracket sequences ")(", "(" and ")" are not.

Let's define the inverse of the bracket sequence as follows: replace all brackets '(' with ')', and vice versa (all brackets ')' with '('). For example, strings "()((" and ")())" are inverses of each other.

You are given a regular bracket sequence $s$. Calculate the number of pairs of integers $(l,r)$ ($1 \le l \le r \le |s|$) such that if you replace the substring of $s$ from the $l$-th character to the $r$-th character (inclusive) with its inverse, $s$ will still be a regular bracket sequence.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The only line of each test case contains a non-empty regular bracket sequence; it consists only of characters '(' and/or ')'.

Additional constraint on the input: the total length of the regular bracket sequences over all test cases doesn't exceed $2 \cdot 10^5$.

Output

For each test case, print a single integer — the number of pairs $(l,r)$ meeting the conditions from the statement.

Example

input

4
(())
()
()()()
(()())(())

output

1
0
3
13

Note

In the first example, there is only one pair:

  • $(2, 3)$: (()) $\rightarrow$ ()().

In the second example, there are no pairs.

In the third example, there are three pairs:

  • $(2, 3)$: ()()() $\rightarrow$ (())();
  • $(4, 5)$: ()()() $\rightarrow$ ()(());
  • $(2, 5)$: ()()() $\rightarrow$ (()());

 

解题思路

  先给出我的做法,应该还有更简洁的方法,等官方题解出了再补。

  如果一个括号序列是合法的,那么必然满足以下 $2$ 个条件:

  1. 在任意一个前缀中 ( 的数量不小于 ) 的数量。
  2. 整个序列的 ( 和 ) 数量相等。

  现在把 ( 和 ) 分别看作 $1$ 和 $-1$,对序列求一个前缀和,记为 $s_i$。考虑枚举反转区间的左端点 $l$,那么哪些右端点 $r \, (i \leq r \leq n)$ 使得将区间 $[l,r]$ 内的括号反转后,整个括号序列仍是合法的?

  先满足第 $1$ 个条件。如果反转区间 $[l,r]$,那么前缀会受到影响的位置就是 $k \in [l,r]$,下标为 $k$ 的前缀会变成 $s_{l-1} - (s_{k} - s_{l-1}) = 2 \cdot s_{l-1} - s_k$。如果第条件 $1$ 要满足,那么对于每个 $k$ 都必须有 $2 \cdot s_{l-1} - s_k \geq 0 \Rightarrow s_k \leq 2 \cdot s_{l-1}$,即 $\max\limits_{l \leq k \leq r}\{ s_k \} \leq 2 \cdot s_{l-1}$。为此当固定 $l$ 后,可以在区间 $[l,n]$ 内二分出最远且合法的右端点 $r$,check 的时候需要快速知道某个区间内 $s_i$ 的最大值,这个可以用 RMQ 或线段树来维护。

  最后是满足第 $2$ 个条件。现在我们确定了最远的位置 $r$,但并不是所有位于 $[l,r]$ 区间内的下标都适合作为反转区间的右端点。显然反转区间内的 ( 和 ) 的数量必须相同,因此合法的右端点 $k \in [l,r]$ 还需要满足 $s_k - s_{l-1} = 0$。所以我们现在需要统计在 $l \leq k \leq r$ 内有多少个位置满足 $s_k = s_{l-1}$,该结果就是以 $l$ 为左端点的合法反转区间数量。方法很简单,只需在预处理 $s_i$ 时开个哈希表存储每个前缀值对应的下标。然后在前缀为 $s_{l-1}$ 的下标中二分出大于等于 $l$ 的最小位置 $x$,以及小于等于 $r$ 的最大位置 $y$,合法的右端点数量就是 $y-x+1$。

  AC 代码如下,时间复杂度为 $O(n \log n)$:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 5;

char str[N];
int s[N];
int f[18][N];

int query(int l, int r) {
    int t = __lg(r - l + 1);
    return max(f[t][l], f[t][r - (1 << t) + 1]);
}

void solve() {
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    map<int, vector<int>> mp;
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + (str[i] == '(' ? 1 : -1);
        mp[s[i]].push_back(i);
    }
    for (int i = 0; 1 << i <= n; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            if (!i) f[i][j] = s[j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
        }
    }
    LL ret = 0;
    for (int i = 1; i <= n; i++) {
        int l = i, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (query(i, mid) <= s[i - 1] << 1) l = mid;
            else r = mid - 1;
        }
        if (query(i, l) <= s[i - 1] << 1) {
            int x = lower_bound(mp[s[i - 1]].begin(), mp[s[i - 1]].end(), i) - mp[s[i - 1]].begin();
            int y = upper_bound(mp[s[i - 1]].begin(), mp[s[i - 1]].end(), l) - mp[s[i - 1]].begin() - 1;
            if (x <= y) ret += y - x + 1;
        }
    }
    printf("%lld\n", ret);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    
    return 0;
}

 

参考资料

  Educational Codeforces Round 166 [Rated for Div. 2]:https://codeforces.com/blog/entry/129909

标签:Invertible,sequence,int,leq,Bracket,端点,Sequences,regular,bracket
From: https://www.cnblogs.com/onlyblues/p/18224674

相关文章

  • QOJ 4824 Bracket-and-bar Sequences
    考虑到这个实际上没有特别好的表示方法。不如从\(n\le25\),猜想合法的序列数量不多。考虑对这个计数。类似于合法括号序计数,考虑把串拆为\(\texttt{(}\cdots\texttt{|}\cdots\texttt{)}\cdots\)来考虑。那么令\(f_i\)表示\(i\)对\(\texttt{(|)}\)组成的序列的数量。......
  • 翻译《The Old New Thing》- Consequences of the scheduling algorithm: Low priorit
    Consequencesoftheschedulingalgorithm:Lowprioritythreadscantake100%CPU-TheOldNewThing(microsoft.com)https://devblogs.microsoft.com/oldnewthing/20071220-00/?p=24093 RaymondChen 2007年12月20日调度算法的控制:低优先级线程也可能占用100%的......
  • [491] Non-decreasing Subsequences
    算法助手用户:这个题目有什么好的思路吗?“Givenanintegerarraynums,returnallthedifferentpossiblenon-decreasingsubsequencesofthegivenarraywithatleasttwoelements.Youmayreturntheanswerinanyorder.”我的代码是这样的:/**@lcapp=leetcod......
  • P4143PyramidSequences
    数学等价于在一个\(n\timesm\)的矩形中做弹球,问经过的整点个数\(t=gcd(n,m)\),将\(n,m\)分别除掉\(t\),得到\(n',m'\)此时会有\(n'm'\)条线段,每条线段经过\(t\)个整点,另外还有\(\lceil\frac{(n'+1)(m'+1)}{2}\rceil\)个交点所以最终答案为\[\lceil\frac{(n......
  • ANSI 转义序列(ANSI Escape Sequences)
    本文来自GithubGistfrom"fnky/ANSI.md"。下面是笔者翻译版本。持续更新中。ANSI转义序列标准Esc代码以Escape为前缀:Ctrl快捷键:^[八进制:\033Unicode:\u001b十六进制:\x1B十进制:27后面跟着命令,有时用左方括号([)分隔,称为控制序列引导码(CSI),后面可选地跟着......
  • CF1924D Balanced Subsequences 题解
    先判掉\(k>\min(n,m)\)的情况。首先有个明显的计算最长合法括号子序列的贪心方法:初始一个值为\(0\)的计数器,从左到右枚举每个字符,遇到(时将计数器加一,遇到)时如果计数器不为\(0\)就减一然后将答案加一。考虑绘制它的折线图。初始时纵坐标为\(0\),从左到右枚举每个字符......
  • [hdu6647]Bracket Sequences on Tree 解题报告
    oj:https://gxyzoj.com/d/hzoj/p/3575因为自己的脑残原因,调了8个小时啊!!!切入正题Part1假定1为根,可以发现,如果u的两棵子树同构,则他们遍历的顺序不影响答案所以,就可以将子树按哈希值分类,这道题就变成了一个可重复组合问题,设\(f_i\)表示以1为根时i的方案数,\(a_i\)表示某一种哈......
  • CF1922E Increasing Subsequences
    一个显然的思路就是构造很多互不相关的上升序列。但是这样构造出来的\(n\)是\(O(\log_2^2n)\)量级的,所以需要考虑新做法。假设我们本来有一个上升序列,我们能否往里面插数?如果插入的数前面本来有\(x\)个数,那么它有\(2^x\)的贡献。于是容易想到先写一个最大的上升序列,再二......
  • E. Increasing Subsequences__2
    原题链接题解已知对于一个长度为\(n\)的连续+1型上升序列而言,其满足要求的子序列有\(2^n\)个若我们在该序列下标为\(k\)的右边插入一个绝对大于左边,绝对小于右边的数,满足要求的子序列会增加\(2^k\)个由此想到极限构造加二进制,其中最高位的一不用管,其余的每一位生成上升......
  • ARC173D-Bracket Walk
    题意给定一个\(n\)个点\(m\)条边的有向强联通图,每条边为'('或')',问是否存在一条回路,使得每条边至少经过一次,且路径的边按顺序拼接后形成的字符串为合法括号序列输出'Yes'or'No'\(n\le4000\)、\(m\le8000\)做法边'('、')'分别替换成权值\(+1,-1\)观察1:题意可以转化成:找......