Заменим открывающуюся скобку на 1, закрывающуюся на -1. Например, (()) это (1,1,-1,-1)
Критерий правильной СП: Все префиксные суммы неотрицательны, и вся сумма равна нулю. Для (()) префиксные суммы это (1,2,1,0).
Сделаем дерево отрезков на n элементов, где n — длина всей строки. В каждой ячейке будем хранить префиксную сумму. Обновление: pref[i], pref[i+1]..pref[n] или увеличатся на 2, или уменьшатся на 2, в зависимости от изначального типа s[i]. Это можно сделать обновлением на отрезке в до.
Запросы проверки: нужно проверить, что min(l-1,l-1)=min(r,r) (pref[l-1]=pref[r]) и min(l,r)>=min(l-1,l-1) (минимальная из префиксных сумм неотрицательна). Здесь min(a,b) — минимум на отрезке [a,b], может быть найден с помощью дерева отрезков.

Эта задача — дикий баян, и была в 223 раунде codeforces. 380C. Сережа и скобочки. Идея решения в разборе немного проще, чем предложил BOOBA, и ни к каким префикс-суммам с использованием этой идеи переходить не надо. Подстрока $$$\left[l,r\right]$$$ является правильной скобочной последовательностью если ее максимальная правильная скобочная подпоследовательность имеет длину $$$r-l+1$$$.