首先，定义的平衡括号中的字符串作为字符串，从而   对于每一个（有一个独特的，匹配的'）'的地方后   （

First, define a string of "balanced" parentheses as a string such that for every '(' there is one unique, matching ')' somewhere after that '('.

例如，以下字符串都是平衡：

For example, the following strings are all "balanced":

（）

（）（）

（（））（）

，而这些都不是：

）（

（））（

由于字符串括号（长度＆LT; = 1,000,000）和范围查询列表，找到   均衡括号内的每个范围为最大长度   每个＆LT的; = 100,000查询（使用0索引的范围）

Given a string of parentheses (length <= 1,000,000) and a list of range queries, find the maximum length of balanced parentheses within each of the ranges for each of the <= 100,000 queries (using 0-indexing for the ranges)

例如：

（）））（）（（））

范围：[0,3] - >最长= 2：（）

Range: [0,3] -> Longest = 2 : "()"

范围：[0,4] - >最长= 2：（）

Range: [0, 4] -> Longest = 2 : "()"

范围：[5,9] - >最长= 4：（（））

Range: [5, 9] -> Longest = 4: "(())"

我的想法如下：

首先，只是确定字符串是否是平衡，可以通过维持一个堆栈来完成。如果你遇到一个'（'，推入堆栈，你遇到的时候'），弹出堆栈。如果在最后的任何'（的遗体，然后该字符串不是平衡。

First, just determining whether a string is "balanced" can be done by maintaining a stack. If you encounter a '(', push into the stack and when you encounter a ')', pop out of the stack. If at the end any '(' remains, then the string is not "balanced."

不过，重复此为所有范围为O（N * M）的复杂性是太长输入的大小。

However, repeating this for all the ranges is O(N*M) complexity which is too long for the size of the inputs.

现在，当注意到的范围查询，preFIX款项和二进制索引树/段树浮现在脑海中。如果你可以precompute整个preFIX总和范围到一个数组，那么你可以通过采取差别，这将有良好的大O的复杂性发现更小的preFIX款项。

Now, upon noticing the range queries, prefix sums and binary indexed trees/segment trees come to mind. If you can precompute the entire prefix sum range into an array, then you can find smaller prefix sums by taking the difference, which will have good big-o complexity.

我有遇到一个'（'你添加一个到累计和每次分配一个+1值到'（'和值-1到'）'，这样的方式的想法，当你遇到一个'）'你减少。因此，对于一个有效的，平衡的字符串，如））（）您将获得： -1 -2 -1 -2 。

I had the idea of assigning a +1 value to a '(' and a -1 value to a ')' so that way every time you encounter a '(' you add one to the cumulative sum and when you encounter a ')' you decrease. So for a valid, "balanced" string like ))() you would get: -1 -2 -1 -2.

不过，我的问题是你如何使用它来确定它是否是平衡？此外，因为你需要找到一个给定的时间间隔内最大的平衡的字符串，你怎么用的能力，以检查是否给定的子字符串为平衡的发现，给定区间内的这个最大的。

However, my question is how do you use this to determine if it is "balanced"? Also, because you need to find the largest "balanced" string within a given interval, how do you use the ability to check if a given substring is "balanced" to find this largest within that given interval.

推荐答案

简介

对于位置每起支架 X ，要找到匹配的关闭括号在位置是等从 X中的串到是， S [X，Y] ，是平衡的最大子。我们不感兴趣，开始收支架子，因为字符串开始最多有一样好，开始在第一个后续左括号的字符串。

For every starting bracket at position x, you want to find the matching closing bracket at position y, such that the substring from x to y, S[x, y], is the maximum substring that is balanced. We are not interested in substrings starting at closing brackets, because strings starting there are at most as good as strings starting at the first subsequent opening bracket.

最重要的观察是：为每一个左括号开始在某个位置 X'为 X＆LT; X'＆LT;是，匹配的结束括号是 Y'，其中 X'＆LT; Y'＆LT;是。这是因为每一个preFIX S [X，Y] 至少包含尽可能多的打开支架截至收盘括号，所以 S [X' ，Y] 包含的最多的尽可能多的开闭的括号内。

The most important observation is the following: for every opening bracket starting at some position x' for x < x' < y, the matching closing bracket is at y' where x' < y' < y. This is because every prefix of S[x, y] contains at least as many opening brackets as closing brackets, so S[x', y] contains at most as many opening as closing brackets.

我们可以利用这些知识来构建一个树，其中每个节点重新presents最大平衡子，所以它有一个起始位置和结束位置。这个节点重新present孩子们这个顶级子的平衡子。因为可能会出现右括号不匹配的左括号，没有一个统一的根，所以我们实际上有一个森林 1 。

We can use this knowledge to build a tree, where each node represents a maximum balanced substring, so it has a starting position and an end position. The children of this node represent the balanced substrings of this top-level substring. Since there may be closing brackets that do not match an opening bracket, there is no single root, so we actually have a forest1.

一个图片说，一千多字。考虑这个例子：

A picture says more than a thousand words. Consider this example:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
) ) ( ( ) ( ( ) ) )  )  (  (  )  )

这会给下面的树：

   (2, 9)       (11, 14)
   /     \          |
(3, 4) (5, 8)   (12, 13)
          |
       (6, 7)

构建树

构建树是很容易。先建立一个空栈。每当你遇到一个左括号在位置 X ：

Building the tree is really easy. Start with an empty stack. Whenever you encounter an opening bracket at position x:

创建一个节点（X，..） 添加该节点作为节点的当前位于堆栈顶部的孩子（如果存在的话，否则这是一个根） 推新节点在堆栈上

每当你遇到在位置右括号是：

Whenever you encounter a closing bracket at position y:

在弹出的节点（X，..）是在堆栈的顶部（如果没有这样的节点，这是一个无与伦比的结束括号：忽略） 将收盘指数：（X，Y） pop the node (x, ..) that is on top of the stack (if there is no such node, this is an unmatched closing bracket: ignore) set the closing index: (x, y)

您扫描串一次，并在各步骤中进行操作的恒定数量，因此建筑结构中线性时间就完成了。

You scan the string once and perform a constant number of operations in each step, so building the structure is done in linear time.

查询树

现在你需要运行查询。给定一个查询（P，Q），你需要找到最大的节点（这里的大小是Ÿ - X + 1 ），它完全包含在（P，Q）。简单地做了两个二进制搜索找到的开始和结束位置，你的树。 （如果字符位置 P 是您要查找的最小 X＆GT右括号; P 同样，如果该字符位置①是您要查找的最大 Y'其中一个开口支架; P ）求最大间隔沿路径 X 和是。

Now you need to run your queries. Given a query (p, q), you need to find the largest node (where size is y - x + 1) that is fully contained in (p, q). Simply do a two binary searches to find the start and end position in your tree. (If the character at position p is a closing bracket you look for the smallest x > p. Similarly, if the character at position q is an opening bracket you look for the largest y < p.) Find the largest interval along the paths to x and y.

如果你的树是很好的平衡，每个查询需要 O（LG N）的时间。最坏的情况，该字符串开头的所有打开支架，并与所有的右括号结束。然后，查询可能需要线性时间。

If your tree is nicely balanced, each query takes O(lg n) time. Worst case, the string starts with all opening brackets and ends with all closing brackets. Then the query may take up to linear time.

1 我们可以通过添加尽可能多的打开支架字符串的前面，因为有无与伦比的右括号解决这个问题。