Dãy ngoặc đúng trên đoạn
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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 idxhoặc2 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$
Community Discussion