基准时间限制：1 秒 空间限制：131072 KB 分值: 40
有一个括号序列，现在要计算一下它有多少非空子段是合法括号序列。
合法括号序列的定义是：
1.空序列是合法括号序列。
2.如果S是合法括号序列，那么(S)是合法括号序列。
3.如果A和B都是合法括号序列，那么AB是合法括号序列。
Input
多组测试数据。
第一行有一个整数T（1<=T<=1100000），表示测试数据的数量。
接下来T行，每一行都有一个括号序列，是一个由'('和')'组成的非空串。
所有输入的括号序列的总长度不超过1100000。
Output
输出T行，每一行对应一个测试数据的答案。
Input示例
5 ( () ()() (() (())
Output示例
0 1 3 1 2
分析：
这里，我们需要明确区分一个定义，什么叫做子段？什么叫做子序列？子段是子序列的一种，也叫做连续子序列，而子序列呢？如果不要求连续，则是可以从原序列中任意取，但是要保持原先的先后顺序即可。
一个简单的分治，分别控制子段的左右两端点在左右两个区间内，然后从中间开始查找，控制左右两个半区间的合法性即可。
下面给出AC代码：
1 #include <stdio.h> 2 #include <cstring> 3 #include <iostream> 4 #include <string> 5 #include <algorithm> 6 #include <stack> 7 using namespace std; 8 typedef long long ll; 9 const int maxn = 1100005; 10 int dp[maxn]; 11 char s[maxn]; 12 int main (void) 13 { 14 ios::sync_with_stdio(false); 15 int n; 16 scanf("%d",&n); 17 for(int k=1;k<=n;++k) 18 { 19 scanf("%s",s); 20 stack<int>st; 21 int len=strlen(s); 22 for(int i=0;i<len;++i) 23 { 24 if(s[i]==')') 25 { 26 if(st.empty()) 27 continue; 28 int tmp=st.top(); 29 st.pop(); 30 if(tmp!=0) 31 dp[i]=dp[tmp-1]+1; 32 else 33 dp[i]=1; 34 } 35 else 36 st.push(i); 37 } 38 ll ans=0; 39 for(int i=0;i<len;++i) 40 { 41 ans+=dp[i]; 42 dp[i]=0; 43 } 44 printf("%lld\n",ans); 45 } 46 return 0; 47 }