Description

小Y 最近开始学习算法姿势，但是因为小R 非常BB，给了她很多B6 题，所以她觉得自己已经没有什么前途了。于是小R 给了她一些稍微简单的题，让她觉得已经没有什么好害怕的了，其中一道是这样的：

给定一个长度为n 只包含左括号和右括号的序列，现在小R 想要知道经过每一个位置的合法子串有多少个。

空串是一个合法的串，如果A 和B 都是合法的串，那么(A) 和AB 都是合法的串。

 

Input

第一行输入一个正整数T 表示数据组数。接下来T 行每行一个字符串。

Output

对于每组数据，输出一个整数表示答案，令ansi 为经过第i 个位置的子串个数，那么你需要输出

(注意是先求余再求和)

 

Sample Input

1 ()()

Sample Output

20 样例解释： ans 数组为{2,2,2,2}，所以输出20。

 

Data Constraint

对于10% 的数据，n<=100

对于30% 的数据，n <= 1000

对于60% 的数据，n <= 5 <= 10^4

对于100% 的数据，n <= 10^6，1 <= T<= 10

分析

一眼差分

然后比赛的时候居然脑子一抽想不用栈处理括号序列，然后就崩了

其实我们需要记录左括号对应的右括号和右括号对应的左括号即可

然后O(n)扫一遍打上差分标记

没了

 

#include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N=1e6+10;const ll P=1e9+7;char c[N];ll a[N],b[N],next[N],back[N],ans[N];int stack[N],top;int T,n;int main() {    for (scanf("%d",&T);T;T--) {        scanf("%s",c+1);n=strlen(c+1);top=0;        for (int i=0;i