Longest Balanced Subsequence

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

You are given a one-indexed string of brackets of length N. A string of brackets is considered "balanced" if it is classified in one of the three categories listed below:

  1. It is an empty string.
  2. It has the form of (A), where A is a balanced string.
  3. It has the form AB, where A and B are both balanced strings.

For example, ()(()) is balanced, but )()(() is not. A subsequence of a string is a string obtained by deleting some (possibly zero) characters of the string. Please note that a subsequence does not have to be contiguous. You are to write a program that supports Q of the following two operations:

  1. Output the length of the longest balanced subsequence of the substring from index L_i to R_i inclusive.
  2. Flip the bracket located at index P_i. (i.e. from ( to ) and vice versa)


1 \le N, Q \le 10^5

1 \le L_i \le R_i \le N

1 \le P_i \le N

Subtask 1 [30%]

1 \le N, Q \le 10^3

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line of input will contain two integers N and Q, the length of the string and the number of operations.

The second line will contain a string of length N, the initial sequence of brackets. The string will only contain ( and ).

Each of the next Q lines will start with either 1 or 2. If it starts with 1, two integers L_i and R_i will follow. If it starts with 2, one integer P_i will follow.

Output Specification

For each type 1 operation, print one line containing the length of the longest balanced subsequence.

Sample Input

10 7
1 5 8
1 3 6
1 1 10
2 10
1 9 10
2 3
1 1 10

Sample Output



For the first type 1 query, the whole substring (()) is balanced.

For the second type 1 query, there exists no balanced subsequence with positive length.

For the third type 1 query, the required subsequence ()(()) goes from index 1 to 2, then 5 to 8.

For the fourth type 1 query, the whole substring () is balanced after the update.

For the fifth type 1 query, the whole string ()()(())() is balanced after the second update.


There are no comments at the moment.