Обновите и проверьте правильность подстроки, содержащей скобки

Question

Обновите и проверьте правильность подстроки, содержащей скобки

Проблема в:

Дана строка длиной n и m запросов.
Каждый запрос является одним из двух случаев:
- Изменить i-й символ противоположно
- Проверьте, является ли подстрока от u-го до v-го символа правильным выражением в скобках или нет. Если да, выведите 1, иначе выведите 0.

Ограничение по времени: 0,2 с

В этих случаях определяется правильное выражение в скобках:

строка длиной 0
строка содержит только ‘(‘ и ‘)’
если A является правильным выражением в скобках, то (A) также является правильным выражением в скобках
если A и B — правильные выражения в скобках, то AB также является выражением в правильных скобках

Моя основная идея похожа на проблему 380C на CodeForces, http://codeforces.com/blog/entry/10363

Затем я проверяю, равна ли самая длинная подпоследовательность в данных диапазонах длине диапазонов, поэтому я получу ответ. Но я получил ошибку ограничения времени.

Я искал это в Интернете весь день, но у меня нет ответа. Буду благодарен, если вы мне поможете. 🙂

Вот мой код: https://github.com/hoangvanthien/GH_CppFiles/blob/master/SPOJ/NKBRACKE.cpp

1

algorithm c++interval-tree string tree

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Условия для правильной последовательности скобок:

Длина подстроки четная.
Количество открытых и закрытых скобок равно.
В любой точке последовательности нет точки, число закрывающих скобок которой больше числа открытых скобок.

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

Например, для ((())))) -> у нас есть последовательность {1, 2, 3, 2, 1, 0, -1, -2}

Таким образом, для проверки допустимости подстроки, например, подстроки (2, 5), которая ())), мы должны увидеть, если в какой-то момент разница между открытием и закрытием отрицательна. Из приведенной выше последовательности у нас есть {3, 2, 1, 0}, и нам нужно минус 2 для каждого элемента, так как нам нужно убрать те скобки в начале строки, которых нет в подстроке. -> у нас есть {1, 0, -1, -2} -> поэтому подстрока недействительна.

После понимания идеи выше, мы можем найти решение для этой проблемы.

Нам нужна структура данных, которая может быстро обновить диапазон. Например, если мы изменим с ( в ) по индексу 3, поэтому нам нужно минус -2 ко всему элементу от индекса 3 и далее.
И нам нужна структура данных, чтобы быстро возвращать минимальное значение диапазона (нам нужно заботиться только о минимальном значении).

И из всех этих требований мы можем использовать Сегментное дерево, которые дают вам 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

0