更新并检查包含括号的子串是否正确

Question

问题是：

给定长度为n的字符串，m个查询。
每个查询都是两种情况之一：
- 反向改变第i个字符
- 检查从第u个字符到第v个字符的子串是否是正确的括号表达式。如果是，打印 1，否则打印 0。

时限：0.2s

在这些情况下，定义了正确的括号表达式：

长度为0的字符串
一个字符串只包含'('和')'
如果A是正确的括号表达式，则(A)也是正确的括号表达式
如果A和B是正确的括号表达式，那么AB也是正确的括号表达式

我的主要思路和CodeForces上的问题380C类似，http://codeforces.com/blog/entry/10363

然后我检查给定范围内的最长子序列是否等于范围的长度，所以我会得到答案。但是我有时间限制错误。

我整天都在网上搜索这个，但我没有得到答案。如果你能帮助我，我将不胜感激。 :)

这是我的代码：https://github.com/hoangvanthien/GH_CppFiles/blob/master/SPOJ/NKBRACKE.cpp

Answer 1

有效括号序列的条件是：

子串长度为偶数
左括号和右括号的个数相等
在序列中的任何一点，都没有闭括号数大于开括号数的点。

所以，我们可以将原来的开括号和闭括号字符串转换成数字序列，每个数字代表从序列开始开始的开括号和闭括号之间的差值。每个左括号，我们将加一，并为关闭减一。

例如，对于 ((())))) -> 我们有序列 { 1, 2 , 3, 2 , 1, 0, -1, -2 }

所以，要测试一个子串是否有效，例如子串(2, 5)，也就是()))，我们需要看看在任何一点，打开和关闭之间的差异是否为负.从上面的序列中，我们有 {3, 2, 1, 0}，我们需要为每个元素减去 2，因为我们需要从字符串的开头删除那些不在子字符串中的括号。 -> 我们有 {1, 0, -1, -2} -> 所以子字符串无效。

理解了以上思路后，我们就可以有自己的解决方案了。

我们需要的是一个数据结构，可以快速更新一个范围。例如，如果我们在索引 3 处从 ( 更改为 )，那么我们需要从索引 3 开始的所有元素减去 -2。
而我们需要数据结构快速return一个范围的最小值（我们只需要关心最小值）。

根据所有这些要求，我们可以使用 Segment tree，它为您提供 O(log n) 更新和 O(log n) 检索。

伪代码

SegmentTree tree;

Initialize the tree with original sequence

for each query in the tree
   if( query type is update)
      if(change from ) to ()
         increase all value by 2 from range index to n
      else if(change from ( to ) )
         decrease all value by 2 from range index to n
   else
      int min = tree.getMinimumValueInRange(u, v)
      int notInSubstring = tree.getMinimumValueInRange(u - 1, u - 1)
      if(min - notInSubstring < 0)
          print Invalid 
      else if( length of substring is not even)
          print Invalid
      else if( tree.getMinimumValueInRange(v, v) != notInSubstring)//Number of open and close brackets are not equaled.
          print Invalid

更新并检查包含括号的子串是否正确

Update and check if the substring containing brackets is correct

c++

string

algorithm

tree

interval-tree