Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKBRACKE - Dãy ngoặc đúng

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkbracke



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:

-     Xâu rỗng là 1 dãy ngoặc đúng.

-     Nếu A là 1 dãy ngoặc đúng thì (A) là 1 dãy ngoặc đúng.

-     Nếu A và B là 2 dãy ngoặc đúng thì AB là 1 dãy ngoặc đúng.

 

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

-     0 i ch: thay đổi kí tự ở vị trí i của xâu kí tự thành kí tự ch.

-    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.

 

Giới hạn:

      2 <= N <= 100000

      1 <= M <= 200000

      Trong truy vấn loại 1:    1 <= i <= N;              ch là ‘(‘ hoặc ‘)’

      Trong truy vấn loại 2:    1 <= i <= j <= N;

 

Input:

-     Dòng đầu tiên chứa 2 số N, M

-     Dòng tiếp theo chứa N kí tự liên tiếp.

-     M dòng tiếp theo, mỗi dòng chứa 1 truy vấn thuộc 1 trong 2 loại trên.

 

Output:

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

 

 

Ví dụ:

Input

Output

8 7

()))(())

1 1 2

1 3 4

0 3 (

1 1 4

1 5 8

0 6 )

1 5 8

10110

 

 


Được gửi lên bởi:Alex & Friends
Ngày:2012-09-20
Thời gian chạy:0.209s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2012-11-29 13:20:19 Erik
Time sẽ là bình thường, nếu bạn có mẹo giải :D
2012-11-29 04:03:34 Death.Light
Time chặt vãiiiiiiiiiiiiiiiiiiiiiiiii.
2012-11-22 15:32:01 Anh chỉ yêu mình em ...
Để Inline kq sai ngay được.
2012-10-15 03:34:20 HarDToBelieve
buffer + IT -> accepted
2012-09-23 07:55:25 Erik
Accept, IT + BIT :D
Time best :D 8.2s

Last edit: 2012-09-23 12:09:12
2012-09-23 05:28:36 KHD
mình cài BIT và IT mà vẫn tle gần chết , phải tối giản cả lazy update =))

Last edit: 2012-10-03 09:24:11
2012-09-23 05:16:48 Thỏ con làm bánh
segment tree... :D
2012-09-21 16:00:13 Alex & Friends
Rejudged! :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.