BOJ 19851 버거운 버거

문제 링크입니다.

문제 요약

주어진 괄호 문자열에 대해, 다음의 두 쿼리를 처리하세요.

1. 구간 내의 모든 문자를 )에서 (로, (에서 )로 뒤집습니다.
2. 구간 내의 문자열이 올바른 괄호 문자열이 되기 위해 추가해야 하는 최소 문자 수를 구하세요.

풀이

(를 1로, )를 -1로 해석하면 올바른 괄호 문자열이 되기 위한 조건을 다음과 같이 표현할 수 있습니다.

1. 최소 누적 합이 $0$일 것
2. 총합이 $0$일 것

주어진 괄호 문자열의 최소 누적 합을 $a$, 총합을 $b$라고 합시다. 이를 올바른 괄호 문자열로 만들기 위해서는, 우선 최소 누적 합을 $0$으로 만들기 위해 $-a$개의 (를 문자열의 맨 앞에 추가한 뒤, $b-a$의 값에 따라 적절한 괄호를 뒤에 달아 총합을 $0$으로 만들어 주는 것이 최적입니다.

따라서 구간 내 최소 누적 합과 총합을 빠르게 구할 필요가 있습니다. 어떤 구간을 두 소구간으로 나누었을 때, 총합은 두 소구간의 총합의 합이고, 최소 누적 합은 왼쪽의 최소 누적 합과 왼쪽의 총합+오른쪽의 최소 누적합 중 작은 쪽으로 결정됨으로부터, 세그먼트 트리를 끌어올 수 있음을 확인할 수 있습니다.

같은 방식으로 최댓값도 함께 저장해주면 구간 내 모든 문자를 뒤집는 연산 역시 최댓값과 최솟값을 서로 바꾸는 식으로 lazy하게 처리 가능합니다. 따라서 총 시간 복잡도 ${\cal O}((N+Q) \lg N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

struct node{
	int sum, min, max;
};

node tree[4040404]; int lazy[4040404];

void prop(int now, int l, int r){
	if(!lazy[now]) return;
	if(l != r){
		lazy[now<<1] ^= 1;
		lazy[now<<1|1] ^= 1;
	}
	tree[now].sum *= -1;
	tree[now].min *= -1;
	tree[now].max *= -1;
	swap(tree[now].min, tree[now].max);
	lazy[now] = 0;
}

inline void merge(int now){
	tree[now] = {tree[now<<1].sum+tree[now<<1|1].sum, min(tree[now<<1].min, tree[now<<1].sum+tree[now<<1|1].min), max(tree[now<<1].max, tree[now<<1].sum+tree[now<<1|1].max)};
	return;
}

void init(int now, int l, int r, string& s){
	if(l > r) return;
	if(l == r){
		tree[now].sum = tree[now].min = tree[now].max = (s[l-1] == '(' ? 1:-1);
		return;
	}
	init(now<<1, l, mid, s); init(now<<1|1, mid+1, r, s);
	merge(now);
}

void upd(int now, int l, int r, int L, int R){
	prop(now, l, r);
	if(l > R || L > r) return;
	if(L <= l && r <= R){
		lazy[now] ^= 1;
		prop(now, l, r);
		return;
	}
	upd(now<<1, l, mid, L, R); upd(now<<1|1, mid+1, r, L, R);
	merge(now);
}

node qry(int now, int l, int r, int L, int R){
	prop(now, l, r);
	if(l > R || L > r) return {0, 1234567, -1234567};
	if(L <= l && r <= R) return tree[now];
	node lt = qry(now<<1, l, mid, L, R); node rt = qry(now<<1|1, mid+1, r, L, R);
	return {lt.sum+rt.sum, min(lt.min, lt.sum+rt.min), max(lt.max, lt.sum+rt.max)};
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n; string s; cin >> s; init(1, 1, n, s);
	int m; cin >> m; while(m--){
		int q, L, R; cin >> q >> L >> R;
		if(q == 1){
			upd(1, 1, n, L, R);
		}
		if(q == 2){
			node ret = qry(1, 1, n, L, R);
			cout << R-L+1 + ret.sum - 2*min(0, ret.min) << '\n';
		}
	}
}