[백준 19851] 버거운 버거

작성일 | In |

문제 링크

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l + r) >> 1)

struct Node{
	int l[2], r[2], lz;
}t[4004004];

int n, q;
string s;

Node merge(Node L, Node R){
	return {{L.l[0] + max(0, R.l[0] - L.r[0]), L.l[1] + max(0, R.l[1] - L.r[1])}, 
			{R.r[0] + max(0, L.r[0] - R.l[0]), R.r[1] + max(0, L.r[1] - R.l[1])}, 0};
}

Node build(int node = 1, int l = 1, int r = n){
	if(l == r) return t[node] = {{s[l-1] == ')', s[l-1] == '('} , {s[l-1] == '(', s[l-1] == ')'}, 0};
	return t[node] = merge(build(node*2, l, mid), build(node*2+1, mid+1, r));
}

void lazy_update(int node, int l, int r){
	if(t[node].lz){
		swap(t[node].l[0], t[node].l[1]), swap(t[node].r[0], t[node].r[1]);
		if(l != r) t[node*2].lz ^= t[node].lz, t[node*2+1].lz ^= t[node].lz;
		t[node].lz = 0;
	}
}

void update(int nl, int nr, int node = 1, int l = 1, int r = n){
	lazy_update(node, l, r);
	if(r < nl || nr < l) return;
	if(nl <= l && r <= nr){
		t[node].lz = 1;
		lazy_update(node, l, r);
		return;
	}
	update(nl, nr, node*2, l, mid), update(nl, nr, node*2+1, mid+1, r);
	t[node] = merge(t[node*2], t[node*2+1]);
}

Node find(int nl, int nr, int node = 1, int l = 1, int r = n){
	lazy_update(node, l, r);
	if(r < nl || nr < l) return {{0, 0}, {0, 0}, 0};
	if(nl <= l && r <= nr) return t[node];
	return merge(find(nl, nr, node*2, l, mid), find(nl, nr, node*2+1, mid+1, r));
}


int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> s >> q;
	build();

	while(q--){
		int a, l, r; cin >> a >> l >> r;
		if(a == 1){
			update(l, r);
		}else{
			Node k = find(l, r);
			cout << (r - l + 1) + k.l[0] + k.r[0] << "\n";
		}
	}
}

여담

이 문제의 코드를 약간만 수정해서 17407. 괄호 문자열과 쿼리를 풀 수 있습니다.

```