Bedao Mini Contest 24 - BRACKETQUERY

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một xâu ~S~ độ dài ~N~ chỉ gồm các ký từ '('')'.

Bạn được cho ~Q~ truy vấn, truy vấn thứ ~i~ thuộc một trong hai dạng sau:

  • ~1~ ~x~: Nếu ~S_x~ là '(' thì ~S_x~ sẽ trở thành ')'. Nếu ~S_x~ là ')' thì ~S_x~ sẽ trở thành '('.

  • ~2~ ~x~: Tìm độ dài dãy ngoặc đúng dài nhất bắt đầu tại vị trí ~x~.

Ta định nghĩa một dãy ngoặc đúng như sau:

  • Nếu ~A~ rỗng thì ~A~ là một dãy ngoặc đúng

  • Nếu ~A~ là một dãy ngoặc đúng thì ~(A)~ cũng là một dãy ngoặc đúng

  • Nếu ~A~, ~B~ là dãy ngoặc đúng thì ~AB~ cũng là một dãy ngoặc đúng

Một vài ví dụ cho dãy ngoặc đúng: "(())()", "((()))", "()()()".

Input

Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~Q~ ~(1 \le N, Q \le 5 \cdot 10^5)~.

Dòng thứ hai chứa xâu ~S~.

~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~t~ và ~x~ ~(t \in {1, 2}, 1 \le x \le N)~.

Output

Với mỗi truy vấn ~t = 2~, in ra độ dài dãy ngoặc đúng dài nhất bắt đầu tại vị trí ~x~ trên một dòng.

Scoring

Subtask Điểm Giới hạn
1 ~20\%~ ~n, q \le 1000~.
2 ~30\%~ ~n, q \le 10^5~
3 ~50\%~ Không có ràng buộc gì thêm.

Sample Input 1

3 4
(()
2 1
2 2
1 2
2 1

Sample Output 1

0
2
2

Sample Input 2

8 6
)((())()
2 3
1 7
2 2
2 1
1 1
2 1

Sample Output 2

6
6
0
8

Notes

Trong test ví dụ đầu tiên:

  • Ở truy vấn thứ ~1~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 1~ là ~\varnothing~.

  • Ở truy vấn thứ ~2~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 2~ là "()".

  • Ở truy vấn thứ ~3~, ~S~ đổi thành "())".

  • Ở truy vấn thứ ~4~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 1~ là "()".


Comments

Please read the guidelines before commenting.



  • 5
    y  commented on May 2, 2024, 8:33 a.m. edited

    Em nghĩ TL bài này hơi chặt, tại em copy code mẫu nộp lên vẫn TLE ạ T_T