2

问题是：

  • 给定长度为 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

4

1 回答 1

1

有效括号序列的条件是：

  • 子串的长度是偶数。

  • 开括号和右括号的数量相等。

  • 在序列中的任何点，没有一个点的右括号数大于左括号数。

所以，从原来的开闭括号串，我们可以把它转换成数字序列，每个数字代表从序列开始的开括号和右括号的区别。每个开括号，我们将加一，减一为关闭。

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

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

了解了上面的思路后，我们就可以有解决问题的办法了。

  • 我们需要的是一个可以快速更新范围的数据结构。例如，如果我们在索引 3 处从(to更改)，那么我们需要-2从索引 3 开始减去所有元素。

  • 而我们需要数据结构快速返回一个范围的最小值（我们只需要关心最小值）。

根据所有这些要求，我们可以使用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
于 2015-12-16T05:29:27.143 回答