Informatica Online Judge

  괄호와 쿼리 [2506 / 09CA]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 1   Total Tried : 1


The Champion of this Problem (C++) : gs18115 - 327ms / 6264byte
My Best Submission (C++) : N/A

[36th 최은수(gs18115)]

Background

빈 괄호 문자열이 $N$개가 있다.
당신은 다음 4가지 연산을 시행한다.
0. $x$번 괄호 문자열에 괄호 $p$를 삽입하여 $i$번째 자리에 위치하도록 한다.
1. $x$번 괄호 문자열의 $i$번째 자리에 있는 괄호를 삭제한다.
2. $y$번 괄호 문자열을 $x$번 괄호 문자열 뒤에 붙인다. $y$번 괄호 문자열은 이후 연산에서 더 이상 주어지지 않는다.
3. $x$번 괄호 문자열의 $[l,r]$ 구간에 속하는 괄호를 모두 뒤집는다. 즉, "("는 ")"으로, ")"는 "("으로 바꾼다.

올바른 괄호 문자열은 다음과 같이 정의된다.
0. 빈 문자열은 올바른 괄호 문자열이다.
1. $S$가 올바른 괄호 문자열이면 $(S)$도 올바른 괄호 문자열이다.
2. $S$와 $T$가 올바른 괄호 문자열이면 $ST$도 올바른 괄호 문자열이다.
3. 위 3개 규칙으로 만들어질 수 없는 괄호 문자열은 올바르지 않은 괄호 문자열이다.

각 괄호 문자열의 자리는 길이를 $s$라 할 때 왼쪽부터 순서대로 0부터 $s-1$까지 매겨진다.

괄호 문자열을 $S_0 S_1 ... S_{s-1}$이라 하면, shift는 $S_n S_{n+1} ... S_{s-1} S_0 S_1 ... S_{n-1}$이 된다.
이 때, $s$는 문자열의 길이이고 자연수 $n$은 $n < s$를 만족하며, $S_x$는 문자열의 $x$번 문자이다.

연산을 시행할 때마다, 당신은 $x$번 괄호 문자열을 shift할 때 올바른 괄호 문자열이 되는 $n$의 수를 구해야 한다.

Input

괄호 문자열의 개수 $N$과 연산의 개수 $Q$가 주어진다. ($1 \leq N, Q \leq 2x10^5$)
다음 $Q$개의 줄에는 3개 또는 4개의 숫자가 주어진다.
처음에는 연산의 종류 $t$가 주어진다. ($0 \leq t \leq 3$)
$t=0$일 경우 $x, i, p$가 주어진다. ($0 \leq x < N$, $0 \leq i \leq s_x$, $p="("$ 또는 $p=")"$ )
$t=1$일 경우 $x, i$가 주어진다. ($0 \leq i < s_x$ )
$t=2$일 경우 $x, y$가 주어진다. ($0 \leq x, y < N, x \neq y$)
$t=3$일 경우 $x, l, r$이 주어진다. ($0 \leq x < N, 0 \leq l \leq r < s_x$)
모든 입력은 자연수이며, $s_x$는 $x$번 문자열의 길이이다.

Output

$Q$개의 연산마다 답을 한 줄에 하나씩 출력한다.

IO Example

입력
2 3
0 0 0 (
0 1 0 )
2 1 0

출력
0
0
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]