问题是:

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

    最佳答案

    有效括号序列的条件是:

  • 子字符串的长度是偶数。
  • 开括号和闭括号的数量相等。
  • 在序列的任何一点上,都没有哪个括号括起来的数字大于括号括起来的数字。

  • 因此,从原始的左括号和右括号开始,我们可以将其转换为数字序列,每个数字代表从序列开头的右括号和右括号之间的差异。每个方括号中,我们将加一个,而负号则作为关闭。

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

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

    了解了以上想法后,我们就可以对问题进行解决。
  • 我们需要一个数据结构,它可以快速更新范围。例如,如果我们从索引3的(更改为),那么我们需要将-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
    

    关于c++ - 更新并检查包含方括号的子字符串是否正确,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/34303769/

    10-11 22:45
    查看更多