Bedao Mini Contest 24 - BRACKETQUERY
View as PDF
Cho một xâu ~S~ độ dài ~N~ chỉ gồm các ký từ '(' và ')'.
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
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