Как быстро проверить правильная ли скобочная последовательность?
Единственное условие корректности - счет кол-ва закрытых скобок не должен превышать счета открытых. Храните для каждой позиции адрес ближайшей справа с единичной ("+1") или нулевой ("0") суммой счета. Поскольку инверсия с открывающей на закрывающую уменьшает все счетчики вправо до второй инверсии на "-2", Вам остается проверить была ли вторая инверсия парной, и не оказалось ли ячейки единичного/нулевого счета между ними.
P.S. Парная инверсия, в которой левая замена с закрывающей на открывающую, как у Вас в примере, кажется мне валидной всегда.
 Если изначально последовательность правильная - любая инверсия приводит к ее порче; Если инверсии было две - последовательность может быть правильной, только когдаИнвертировались скобки разного типа ('(' и ')') Между ними должно быть четное количество других скобок
Если хоть что-то из перечисленного не выполняется, то последовательность не является правильной, при этом их проверка требует константное время. 
Если выполняется все - нужно использовать доволнительную структуру и следующий алгоритм:Предположим, что скобочная последовательность хранится в виде массива, элементами которого являются скобки, для каждой из которых хранится индекс ее пары (соответствующей закрывающей/открывающей скобки)При каждой инверсии будем затирать для соответствующих скобок (открывающая/закрывающая) индексы и помечать ихТак как инверсии было две, то получим 4 помеченных индекса. В силу того, что инвертировались разные типы скобок, среди них будут либо образовываться две новые пары, не противоречащие правильности последовательности (проверяется это травиально), либо нет
Быстрее ничего придумать не получается. Единственное тонкое место - проверка в последнем пункте, так как в различных случаях может занимать как константное время, так и O(k), где k строго меньше n и в среднем случае является логарифмом.