괄호문자열 만들기

처음 $i$개 문자의 여는 괄호 수에서 닫는 괄호 수를 뺀 값을 $S_i$라 하자. 구간 $[l,r]$이 올바른 괄호 문자열이라는 조건은

$$S_{l-1}=S_r,\qquad S_j\geq S_{l-1}\quad(l\leq j\leq r)$$

이다. 경계 $0,\ldots,N$을 정점으로 보고, 각 지정 구간의 두 경계 $l-1,r$을 DSU로 합친다.

서로 다른 집합의 경계가 $x_1<y_1<x_2<y_2$ 순서로 교차한다면 두 집합도 합친다. 이를 위해 경계를 왼쪽부터 훑으며 아직 마지막 경계에 도달하지 않은 집합들을 스택에 둔다. 집합이 다시 나타나면 그 위의 집합들을 모두 합치고, 마지막 경계에 도달한 집합은 스택에서 뺀다.

최종 집합마다 연속한 경계 사이의 구간을 만들면, 구간들은 서로 떨어져 있거나 포함 관계에 있다. 각 구간에서 바로 안쪽의 구간들을 제거하고 남은 위치들을 순서대로 묶는다. 각 묶음을 독립적으로 올바른 괄호 문자열로 만들면 된다. 어느 구간에도 속하지 않는 위치는 $\max(a_i,b_i)$를 선택한다.

한 묶음의 길이를 $2k$라 하자. 모두 닫는 괄호로 두면 보상은 $\sum b_i$이고, 위치 $i$를 여는 괄호로 바꿀 때의 이득은 $a_i-b_i$이다. 왼쪽부터 이득을 최대 힙에 넣고, 묶음의 첫째·셋째·다섯째 위치마다 최댓값 하나를 꺼내 여는 괄호로 선택한다.

묶음들의 전체 크기는 $N$ 이하이다. 시간 복잡도는 $O((N+M)\alpha(N)+N\log N)$, 공간 복잡도는 $O(N+M)$이다. 는 역 아커만 함수이다.

증명

같은 DSU 집합의 경계들은 높이가 같다. 원래 구간들이 이어서 덮는 범위에서는 그 높이 아래로 내려갈 수 없으므로, 연속한 두 경계 사이도 올바른 괄호 문자열이어야 한다. 서로 다른 집합의 경계가 교차하면 접두사 조건에 의해 서로의 높이가 상대방 이상이어야 한다. 따라서 두 높이는 같고, 집합을 합쳐도 조건이 달라지지 않는다.

교차를 모두 없애면 구간들은 서로 떨어져 있거나 포함 관계에 있다. 올바른 괄호 문자열을 삽입하거나 제거해도 바깥 문자열의 올바름은 유지된다. 따라서 원래 조건은 각 구간에서 안쪽 구간을 제거한 묶음들을 독립적으로 올바르게 만드는 조건과 동치이다.

한 묶음의 처음 $2j-1$개 위치에는 여는 괄호가 적어도 $j$개 필요하다. 이전 탐욕 선택들을 포함하는 최적해에서, 이 접두사 안의 추가 선택 하나를 현재 힙의 최댓값으로 바꾸자. 앞선 접두사는 이전 선택들만으로 조건을 만족하고, 이후 접두사의 선택 수는 변하지 않으므로 보상이 줄지 않는 교환이다. 따라서 탐욕법이 최적이다.