동시에 균형을 이루는 괄호 문자열

시간 제한1초메모리 제한128 MB

요약

길이 N인 K개의 괄호 문자열이 주어질 때, 모든 문자열에서 동시에 올바른 괄호열이 되는 부분 구간의 개수를 센다.

난이도: 보통10점 중 7점
유형: 해시맵, 누적 합, 분할 정복, 수학
정답자: 아직 제출이 없습니다

문제

길이가 모두 $N$ 인 괄호 문자열 $K$ 개가 주어진다 ( $1 \le K \le 10$ , $1 \le N \le 50000$ ). 각 문자열을 $S_1, S_2, \dots, S_K$ 라 하고, 각 문자열의 문자는 $0$ 번부터 $N-1$ 번까지 번호가 매겨져 있다.

구간 $i \dots j$ ( $0 \le i \le j \le N-1$ )가 동시에 균형을 이룬다는 것은, 모든 문자열 $S_1, \dots, S_K$ 에 대해 위치 $i$ 부터 $j$ 까지의 부분 문자열이 각각 균형 잡힌 괄호 문자열임을 뜻한다.

예를 들어 $K = 3$ 이고 문자열이 다음과 같다고 하자.

S_1 = )()((())))(())
S_2 = ()(()()()((())
S_3 = )))(()()))(())
                1111
      01234567890123

이때 구간 $3 \dots 8$ 은 동시에 균형을 이룬다. $S_1[3\dots8] = ((()))$ , $S_2[3\dots8] = ()()()$ , $S_3[3\dots8] = (()())$ 가 모두 균형 잡힌 문자열이기 때문이다. 구간 $10 \dots 13$ 과 $11 \dots 12$ 역시 동시에 균형을 이룬다.

구간 $i \dots j$ 가 동시에 균형을 이루는 쌍 $(i, j)$ 의 개수를 세어라.

괄호 문자열이 균형 잡혀 있다는 것은, (와 )의 개수가 같고 모든 접두사에서 (의 개수가 )의 개수 이상임을 뜻한다. 예를 들어 다음 문자열들은 균형 잡혀 있다.

()
(())
()(()())

반면 다음 문자열들은 그렇지 않다.

)(
())(
((())))

입력

첫째 줄: 두 정수 $K$ 와 $N$ .
둘째 줄부터 $K+1$ 번째 줄까지: 각 줄에 길이 $N$ 인 괄호 문자열이 하나씩 주어진다.

출력

동시에 균형을 이루는 구간 $(i, j)$ 의 개수를 정수 하나로 출력한다.

예제4

예제 1

입력

3 14
)()((())))(())
()(()()()((())
)))(()()))(())

예상 출력

예제 2
입력
```
1 2
()
```
예상 출력
```
1
```
예제 3
입력
```
1 4
(())
```
예상 출력
```
2
```
예제 4
입력
```
2 4
(())
()()
```
예상 출력
```
1
```