C. Bracket Sequences Concatenation Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
题目链接

A bracket sequence is a string containing only characters "(" and ")".

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 "()()", "(())" are regular (the resulting expressions are: "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

You are given nn bracket sequences s1,s2,…,sns1,s2,…,sn. Calculate the number of pairs i,j(1≤i,j≤n)i,j(1≤i,j≤n) such that the bracket sequence si+sjsi+sj is a regular bracket sequence. Operation ++ means concatenation i.e. "()(" + ")()" = "()()()".

If si+sjsi+sj and sj+sisj+si are regular bracket sequences and i≠ji≠j, then both pairs (i,j)(i,j) and (j,i)(j,i) must be counted in the answer. Also, if si+sisi+si is a regular bracket sequence, the pair (i,i)(i,i) must be counted in the answer.

Input

The first line contains one integer n(1≤n≤3⋅105)n(1≤n≤3⋅105) — the number of bracket sequences. The following nn lines contain bracket sequences — non-empty strings consisting only of characters "(" and ")". The sum of lengths of all bracket sequences does not exceed 3⋅1053⋅105.

Output

In the single line print a single integer — the number of pairs i,j(1≤i,j≤n)i,j(1≤i,j≤n) such that the bracket sequence si+sjsi+sj is a regular bracket sequence.

Examples
input
Copy 
3
)
()
(
output
Copy 
2
input
Copy 
2
()
()
output
Copy 
4
Note

In the first example, suitable pairs are (3,1)(3,1) and (2,2)(2,2).

In the second example, any pair is suitable, namely (1,1),(1,2),(2,1),(2,2)(1,1),(1,2),(2,1),(2,2).


题解：

统计左括号的个数，当出现右括号时，若左括号数不为0，则左括号数自减，否则右括号数加一。

统计最后的结果，只有当左右括号数中一个为0时，放入数组中。

最后统计结果。

((()
l 2
r 0

))(()))
l 0
r 3

()()
l 0
r 0


a[2]++;
b[3]++;
c++;

for (int i = 0; i < MAXN; i++)
	if (a[i] && b[i])
		ans += a[i] * b[i];

cout << ans + c * c << endl;

注意：

long long int sum=150000* 150000;    //这样结果会溢出

sum=(long long int )150000 * (long long int )150000    //必须（long long int）

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
long long int a[400000],b[400000],c=0;
int main()
{
	long long int n,sum=0;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		long long int l=0,r=0;
		char s[400000];
		cin>>s;
		int slen=strlen(s);
		for(int j=0;j<slen;j++)
		{
			if(s[j]==')'&&l)
			{
				l--;
			}
			else if(s[j]==')')
			{
				r++;
			}
			else
			{
				l++;
			}	
		}
		if(r==0&&l!=0)
		{
			a[l]++;
		}
		else if(l==0&&r!=0)
		{
			b[r]++;
		}
		else if(l==0&&r==0)
		{
			c++;
		}
	} 
	for(int i=0;i<300000;i++)
	{
		if(a[i]&&b[i])
		{
			sum+=a[i]*b[i];
		}
	}
	sum+=(long long int )c*(long long int )c;
	//sum=(long long int )150000 * (long long int )150000;
	cout<<sum<<endl;
	return 0;
}