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
2021-05-27 18:02:14
Tham khảo: https://vnspoj.github.io/problems/NKBRACKE
2019-12-22 03:33:43
Segment tree
CLQD K12
2018-10-19 04:49:10
IT+Lazy 0.81s
CYB =))))))))
2018-10-09 18:19:54
bài này đúng là ko cần LAZY vẫn có thể AC !
2017-12-18 11:08:17
1 đấm AC ~.~
Ko cần lazy
frostpixel aka.How 2 AC
2017-11-26 11:12:42
nhật hào sạch
2017-09-06 03:36:35
mình dùng chăm-chỉ-update cơ
2017-09-06 03:36:14
sao các bạn lười update thế
2017-09-05 14:38:59
:V vãi, thêm ios::sync... với phải thêm cin.tie(0) nữa mới AC :V vkl
2017-07-06 08:09:24
ai dùng c++ đừng sử dụng cin hay cout nhá chuyển sang scanf và printf mới ac
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.