Длина самой длинной цепочки сбалансированных скобок в заданных диапазонах

Question

Во-первых, определите строку "сбалансированных" скобок как строку, такую, что для каждого "(" есть один уникальный, соответствующий ")" где-то после этого "(".

Например, следующие строки все "сбалансированы":

()

() ()

(()) ()

пока это не так:

) (

()) (

Учитывая строку скобок (длина <= 1000 000) и список запросов диапазона, найдите максимальную длину сбалансированных скобок в каждом из диапазонов для каждого из <= 100 000 запросов (используя 0-индексирование для диапазонов)

Пример:

())) () (())

Диапазон: [0,3] -> Самый длинный = 2: "()"

Диапазон: [0, 4] -> Longest = 2: "()"

Диапазон: [5, 9] -> самый длинный = 4: "(())"

Мои мысли таковы:

Во-первых, просто определить, является ли строка "сбалансированной", можно, поддерживая стек. Если вы встретите "(", вставьте в стек, а когда встретите ")", выскользните из стека. Если в конце остается какой-либо '(', то строка не "сбалансирована".

Однако повторение этого для всех диапазонов является O(N*M) сложностью, которая слишком велика для размера входов.

Теперь, заметив запросы диапазона, приходят на ум префиксные суммы и деревья / сегментированные деревья с двоичными индексами. Если вы можете предварительно вычислить весь диапазон сумм префиксов в массиве, то вы можете найти меньшие суммы префиксов, взяв разницу, которая будет иметь большую сложность.

У меня была идея присвоить значение +1 для '(' и значение -1 для ')' таким образом, чтобы каждый раз, когда вы сталкиваетесь с '(' вы добавляете единицу к совокупной сумме и когда вы сталкиваетесь с ') "Вы уменьшаете. Таким образом, для правильной, "сбалансированной" строки, как ))() вы получите: -1 -2 -1 -2,

Тем не менее, мой вопрос, как вы используете это, чтобы определить, является ли он "сбалансированным"? Кроме того, поскольку вам нужно найти наибольшую "сбалансированную" строку в заданном интервале, как вы используете возможность проверить, является ли данная подстрока "сбалансированной", чтобы найти это наибольшее значение в этом заданном интервале.

Answer 1

Вступление

Для каждой стартовой скобки в положении x, вы хотите найти соответствующую закрывающую скобку в позиции yтак, что подстрока из x в y, S[x, y]является максимальной подстрокой, которая сбалансирована. Мы не заинтересованы в том, чтобы подстроки начинались с закрывающих скобок, потому что строки, начинающиеся там, не более, чем строки, начинающиеся с первой последующей открывающей скобки.

Наиболее важное наблюдение заключается в следующем: для каждой открывающей скобки, начинающейся в некоторой позиции x' за x < x' < yсоответствующая закрывающая скобка находится на y' где x' < y' < y, Это потому, что каждый префикс S[x, y] содержит как минимум столько открывающих скобок, сколько закрывающих скобок, поэтому S[x', y] содержит максимум столько открывающих, сколько закрывающих скобок.

Мы можем использовать эти знания для построения дерева, где каждый узел представляет максимально сбалансированную подстроку, поэтому у него есть начальная позиция и конечная позиция. Дочерние элементы этого узла представляют сбалансированные подстроки этой подстроки верхнего уровня. Поскольку могут быть закрывающие скобки, которые не соответствуют открывающей скобке, единого корня не существует, поэтому у нас фактически есть лес¹.

Картина говорит более тысячи слов. Рассмотрим этот пример:

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:

• создать узел (x, ..)
• добавить этот узел как дочерний узел узла, который в данный момент находится на вершине стека (если он существует, в противном случае это корень)
• вставить новый узел в стек

Всякий раз, когда вы сталкиваетесь с закрывающей скобкой в ​​позиции y:

• поп узел (x, ..) который находится на вершине стека (если такого узла нет, это непревзойденная закрывающая скобка: игнорировать)
• установить индекс закрытия: (x, y)

Вы сканируете строку один раз и выполняете постоянное количество операций на каждом шаге, поэтому построение структуры выполняется за линейное время.

Опрос дерева

Теперь вам нужно выполнить ваши запросы. Данный запрос (p, q), вам нужно найти самый большой узел (где размер y - x + 1), который полностью содержится в (p, q), Просто выполните два двоичных поиска, чтобы найти начальную и конечную позиции в вашем дереве. (Если персонаж в положении p закрывающая скобка, вы ищете самый маленький x > p, Аналогично, если персонаж на позиции q это открывающая скобка вы ищете самый большой y < p.) Найдите самый большой интервал вдоль путей к x а также y,

Если ваше дерево хорошо сбалансировано, каждый запрос занимает O(lg n) время. В худшем случае строка начинается со всех открывающих скобок и заканчивается всеми закрывающими скобками. Тогда запрос может занять до линейного времени.

¹_{Мы могли бы исправить это, добавив столько открывающих скобок к передней части строки, сколько есть непревзойденных закрывающих скобок.}