a625. C. 括號序列 - 旦旦解題農場

內容

給一個長度為 $ n $ 由 '(' 或 ')' 組成的括號序列，由左到右編號 $ 1 \sim n $，你需要執行下面兩種操作。

詢問一個區間是否合法。
將一個括號取反，即 '(' 變 ')'，')' 變 '('。

一個合法的括號序列定義如下。

空序列是合法的。
若A是合法的，則(A)是合法的。
若A, B是合法的，則AB是合法的。

輸入說明

第一行兩個正整數 $ n, m $ ，代表字串長度和操作次數

第二行一個長度為 $ n $ 的括號字串

接下來 $ m $ 行每行包含2或3個正整數，表示一種操作

$ 1\ l\ r\ $ 詢問區間 $ [l, r] $ 是否為一個合法的括號序列 $ 1 \le l \le r \le n$
$ 2\ i\ $ 將第 $ i $ 個括號取反 $ 1 \le i \le n $

對於 $ 30\% $ 的測資有 $ 1 \le n, m \le 5000 $
對於 $ 70\% $ 的測資有 $ 1 \le n, m \le 4 \times 10^5 $

輸出說明

對於所有操作1輸出一行

若是合法的括號序列請輸出"YES"，否則輸出"NO"

範例輸入

13 10
))()(()(()())
1 2 4
1 8 13
1 5 8
2 8
1 5 8
1 8 13
2 3
1 3 8
2 3
1 3 8

範例輸出

NO
YES
NO
YES
NO
NO
YES

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (10%): 1.0s , <1M
不公開測資點#1 (10%): 1.0s , <1M
不公開測資點#2 (10%): 1.0s , <1M
不公開測資點#3 (10%): 1.0s , <10M
不公開測資點#4 (10%): 1.0s , <10M
不公開測資點#5 (10%): 1.0s , <10M
不公開測資點#6 (10%): 1.0s , <10M
不公開測資點#7 (10%): 1.0s , <10M
不公開測資點#8 (10%): 1.0s , <10M
不公開測資點#9 (10%): 1.0s , <10M

提示：

範例解釋:

詢問 ")()"，一個奇數長度的區間顯然不合法，輸出"NO"

詢問 "(()())"，合法，輸出"YES"

詢問 "(()("，不合法，輸出"NO"

操作後序列變為 "))()(())()())"

詢問 "(())"，合法，輸出"YES"

詢問 ")()())"，不合法，輸出"NO"

操作後序列變為 "))))(())()())"

詢問 "))(())"，不合法，輸出"NO"

操作後序列變為 "))()(())()())"

詢問 "()(())"，合法，輸出"YES"

標籤:

出處:

DDJ Regular Contest Round#5 [管理者：

warner1129 (unknown)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」