Dãy ngoặc đúng

Điểm: 0,60 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một xâu độ dài $N$ chỉ gồm các kí tự '(' và ')', các kí tự được đánh số từ $1$ đến $N$ theo chiều từ trái qua phải.

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

Cho $M$ truy vấn, mỗi truy vấn thuộc $1$ trong $2$ loại sau:

$0$ $i$ $c h$ : thay đổi kí tự ở vị trí $i$ của xâu kí tự thành kí tự $c h$ .
$1$ $i$ $j$ : in ra $1$ nếu xâu con từ vị trí $i$ đến vị trí $j$ là một dãy ngoặc đúng, in ra $0$ trong trường hợp ngược lại.

In ra $0$ hoặc $1$ tương ứng với mỗi truy vấn loại $2$ .

$2 \leq N \leq 100000$

$1 \leq M \leq 200000$

Trong truy vấn loại $1$ : $1 \leq i \leq N$ ; ch là '(' hoặc ')'

Trong truy vấn loại $2$ : $1 \leq i \leq j \leq N$ ;

Copy

Copy

Bình luận

Hãy đọc nội quy trước khi bình luận.