Dãy ngoặc đúng trên đoạn

Buổi 71-72 — Ôn tập Strings
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một xâu $S$ độ dài $N$ chỉ gồm các ký tự ( và ). Có $Q$ truy vấn thuộc một trong hai loại:

  • 1 idx: Đổi ký tự tại vị trí $idx$ (( thành ) hoặc ) thành ().
  • 2 l r: Tìm độ dài của dãy con ngoặc đúng dài nhất (không nhất thiết liên tiếp) trong đoạn $S[l..r]$.
Dữ liệu vào
  • Dòng đầu chứa xâu $S$ ($1 \le |S| \le 10^5$).
  • Dòng thứ hai chứa số nguyên $Q$ ($1 \le Q \le 10^5$).
  • $Q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn (1 idx hoặc 2 l r).
Dữ liệu ra
  • Với mỗi truy vấn loại 2, in ra độ dài dãy ngoặc đúng dài nhất tìm được trên một dòng.
Ví dụ
Input Output
())(())(
3
2 1 8
1 2
2 1 8
6
6
Giới hạn
  • $1 \le |S|, Q \le 10^5$
Draft saved