Ngoặc Đúng Sai

Buổi 27 — Segment Tree cơ bản
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho xâu S độ dài N gồm các ký tự '(' và ')'. Có hai loại thao tác: đảo một ký tự ('(' thành ')' và ngược lại), hoặc kiểm tra xâu con S[l..r] có phải dãy ngoặc đúng (cân bằng) hay không.

Dữ liệu vào

Dòng đầu chứa N và Q. Dòng thứ hai là xâu S. Q dòng tiếp theo:

  • 1 i: đảo ký tự thứ i.
  • 2 l r: kiểm tra.
Dữ liệu ra

Với mỗi truy vấn loại 2, in YES nếu S[l..r] là dãy ngoặc đúng, ngược lại in NO.

Ví dụ
Input Output
5 4\n()(()\n1 3\n1 3\n2 5 5\n1 4 NO
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
Draft saved