문제 링크
https://www.acmicpc.net/problem/19851
풀이
2번 쿼리에서 $[l, r]$구간에서 왼쪽과 오른쪽에 최소 몇개의 괄호를 추가해야 그 구간이 올바른 괄호쌍이 되는지를 구할 수 있다면 구간의 길이에 추가해야 하는 괄호쌍의 개수를 더한 값이 쿼리의 답이 됩니다.
금광 세그 라고 불리는 테크닉을 이용한다면 왼쪽과 오른쪽에 추가해야 하는 괄호의 개수를 관리할 수 있습니다. 세그먼트 트리에서 왼쪽에 추가해야하는 괄호의 개수 $L$, 오른쪽에 추가해야하는 괄호의 개수 $R$, 2가지의 값을 관리하고 두 구간을 합쳐서 만들어지는 새로운 구간에서의 $L, R$값을 구하면 됩니다. 구간의 길이가 $1$일때 해당하는 괄호가 $)$이면 $L=1$, $($이면 $R=1$로 설정합니다. 그리고 두 구간을 합칠 때에는 왼쪽 구간의 $R$과 오른쪽 구간의 $L$이 상쇄되기 때문에 새 구간의 $L, R$은 왼쪽 구간의 $L + max(0,$ 오른쪽 구간의 $L$ - 왼쪽 구간의 $R),$ 오른쪽 구간의 $R + max(0,$ 왼쪽 구간의 $R$ - 오른쪽 구간의 $L)$이 됩니다. 이렇게 모든 구간의 세그먼트 트리를 만들어 놓는다면 $1$번 쿼리가 주어지지 않았을 때에 $2$번 쿼리를 $O(\log N)$에 구할 수 있습니다.
1번 쿼리로 인해 변화하는 값을 관리할 수 있는 방법이 있습니다. 세그먼트 트리를 만들 때 뒤집었을 때의 $fL$과 $fR$을 추가로 저장해 놓는다면 구간이 뒤집혀 있다고 하면 세그먼트 트리에서 $L, R$과 $fL, fR$값을 swap 하기만 하면 됩니다. 이 값들은 구간의 길이가 1일때 $L$과 $R$의 반대로 저장하고 구간을 합칠 때에는 $fL, fR$끼리만 합치면 됩니다. 동일한 구간을 2번 뒤집으면 원래대로 돌아오기 때문에 구간이 뒤집어졌는지 확인하기 위해 $1$번 연산이 들어왔을 때 구간에 $1$을 $xor$해서 현재 구간이 1이면 뒤집어 있는 것이고 0이면 원본 상태라는 것을 알 수 있습니다. 구간에 lazy propagation으로 $xor 1$을 전파해 주면 여러번 뒤집는 연산이 들어오더라도 제대로 값을 유지할 수 있습니다. 1번 연산, 2번 연산 모두 $O(\log N)$이므로 전체 시간복잡도 $O(Q \log N)$입니다.
전체 코드
1 |
|
여담
이 문제의 코드를 약간만 수정해서 17407. 괄호 문자열과 쿼리를 풀 수 있습니다.
```