Editorial

---

D

summary:

bracket sequence 가 있는데, q개의 쿼리에 대해서, 0에서 출발해서 $n-1$번째 인덱스까지 한칸씩 왼쪽이나 오른쪽으로 움직여서 도달하는 경로에 있는 문자들을 이었을 때 regular bracket sequence(짝이 맞는 괄호문자열)이 되는지 구하는 문제이다.

solution:

한가지 관찰해야 할 점은, n이 홀수이면 이동한 경로의 전체 길이도 홀수가 되기 때문에 sequence의 구성에 관계없이 불가능하다는 것이다.

홀수 인덱스에 (, 짝수 인덱스에 )가 존재하는 인덱스의 집합을 $S$라고 하자.(0-indexed)

만약 $min(S)=$짝수라면 가장 앞에 개수가 맞지 않는 )가 존재한다는 뜻이므로 불가능하다.

마찬가지로 $max(S)=$홀수라면 가장 뒤에 개수가 맞지 않는 (가 존재한다는 뜻이므로 불가능하다.

그렇지 않다면 항상 가능한데, ()()(((…)))()() 와 같은 형태일 것이다.

한 번 $\leftrightharpoons$,$\rightleftharpoons$ 이동을 하면 해당 괄호가 짝수 개씩 늘어나는데(왔다 갔다하므로) n이 짝수이므로 (와 )의 차이도 짝수개 나기 때문에 항상 가능하다.