[BOJ] 20052 괄호 문자열 ?

https://www.acmicpc.net/problem/20052

20052번: 괄호 문자열 ?

'('을 1, ')'을 -1이라 가정한다.

만약 어떤 구간 [l,r]이 올바른 괄호 문자열이 아니라면 ')'가 '('보다 많아지는 순간이 있을 것이다.

이를 누적합으로 표현해보면 l부터 누적으로 더하다가 0보다 작아지는 경우와 ')'가 '('보다 많아지는 경우은 동치이다.

따라서 구간의 누적합을 구하고, 누적합들의 최솟값이 0보다 작아지는 경우가 있는지 검사해보는 식으로 바꿀 수 있다.

하지만 모든 구간마다 최대 \(O(N)\) 번 해보게 되어 총 \(O(NQ)\) 가 걸려 TLE가 나게 된다.

 

일단 누적합을 sum배열에 저장해 둔다.

그리고 [l,r] 구간안에서의 sum배열의 최솟값을 구하고, sum[l-1]을 빼주면, [l,r] 구간에서의 누적합 최솟값이 나오게 된다.

이를 통해 누적합 배열을 구하고, 최소 세그먼트 트리를 구성해두면, 각 쿼리당 \(O(logN)\) 의 시간복잡도에 처리할 수 있게 되어 총 \(O((N+Q)logN)\)의 시간복잡도로 문제를 해결 할 수 있다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e18+10;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,sum[100005],t[400005];
char a[100005];

void build(int x,int l,int r) {
	if(l == r) {t[x] = sum[l]; return;}
	int mid = (l + r) >> 1;
	build(x*2,l,mid), build(x*2+1,mid+1,r);
	t[x] = min(t[x*2],t[x*2+1]);
}

int query(int x,int l,int r,int rl,int rr) {
	if(rl > r||l > rr) return INF;
	if(rl <= l&&r <= rr) return t[x];
	int mid = (l + r) >> 1;
	return min(query(x*2,l,mid,rl,rr),query(x*2+1,mid+1,r,rl,rr));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> a+1;
	n = strlen(a+1);
	for(int i = 1;i <= n;i++) sum[i] = sum[i-1]+(a[i] == '(' ? 1 : -1);
	build(1,1,n);
	int Q,ans = 0; cin >> Q;
	while(Q--) {
		int l,r; cin >> l >> r;
		ans += (query(1,1,n,l,r) >= sum[l-1]&&sum[r] == sum[l-1]);
	}
	cout << ans;
}