Another Random Contest 1 P4 - Bracket Query

View as PDF

Submit solution

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

Problem type

A valid bracket sequence consisting of ( and ) is defined as follows:

  • An empty sequence is valid.
  • If X is a valid bracket sequence, then (X) is a valid bracket sequence.
  • If X and Y are valid bracket sequences, then the concatenation of X and Y, Z = X+Y, is a valid bracket sequence.

For example, (()), ()(), and (()())() are all valid bracket sequences, while ( and ()) are invalid bracket sequences.

A professor gave you a sequence of brackets of length N. The professor will ask you Q queries, each consisting of two numbers, l_i and r_i. For each query, you need to check if it is possible to insert a continuous number (possibly zero) of ( or ) brackets into the interval l_i to r_i to make the subsequence valid.

For example:

Let the original string be xxxxxxx.

Then, xxxxx((((((xx or xxxxxxx))))) are all valid insertions.

If it is possible, output YES; otherwise, output NO.


For all subtasks:

1 \le N, Q \le 2 \times 10^5

1 \le l_i \le r_i \le N

Subtask 1 [20%]

1 \le N, Q \le 5 \times 10^3

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line consists of two integers N and Q, the length of the string and the number of queries.

The next line consists of a bracket sequence of length N.

The following Q lines consist of two integers, l_i and r_i.

Output Specification

Output YES and NO on Q separate lines, each line answering a query.

Sample Input

8 8
5 6
2 7
6 7
4 5
5 7
7 8
3 4
6 7

Sample Output



There are no comments at the moment.