백준19851 버거운 버거

작성일 | In

문제 링크

  • http://icpc.me/19851

사용 알고리즘

  • 세그먼트 트리

시간복잡도

  • $O(Q \log N)$

풀이

구간에 있는 빵을 뒤집는 쿼리가 없는 문제를 먼저 해결해봅시다.

구간 $[a,b]$에 최소한의 괄호를 더 추가해서 올바른 괄호 문자열을 만드는 문제고, Prefix Minimum과 Range Sum을 관리해야 한다는 것은 쉽게 알 수 있습니다. 구간의 Prefix Minimum을 $mn$, Range Sum을 $sum$이라고 하면, 우리가 추가해야 하는 괄호의 개수는 $sum + 2\cdot\min(mn, 0)$입니다. 이러한 형태의 값은 세그먼트 트리를 이용해 쉽게 계산할 수 있습니다.

구간에 있는 빵을 뒤집는 것은 구간에 있는 모든 원소에 -1을 곱하는 것과 같습니다. 그러므로 Prefix Minimum 뿐만 아니라 Prefix Maximum도 관리해야 구간에 -1을 곱하는 쿼리도 올바르게 처리할 수 있습니다. 간단한 Lazy Propagation 문제입니다.

전체 코드

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
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

struct Node{
    int mn, mx, sum;
    Node() : Node(0) {}
    Node(int v) : Node(v, v, v) {}
    Node(int mn, int mx, int sum) : mn(mn), mx(mx), sum(sum) {}
} T[1 << 21];
Node operator + (const Node &a, const Node &b){
    return { min(a.mn, a.sum + b.mn), max(a.mx, a.sum + b.mx), a.sum + b.sum };
}

int N, Q, L[1 << 21];
string S;
void Push(int node, int s, int e){
    if(!L[node]) return;
    T[node].sum *= -1;
    T[node].mn *= -1;
    T[node].mx *= -1;
    swap(T[node].mn, T[node].mx);
    if(s != e) L[node<<1] ^= 1, L[node<<1|1] ^= 1;
    L[node] = 0;
}
void Init(int node=1, int s=1, int e=N){
    if(s == e){
        T[node] = Node(S[s] == '(' ? 1 : -1);
        return;
    }
    int m = s + e >> 1;
    Init(node<<1, s, m); Init(node<<1|1, m+1, e);
    T[node] = T[node<<1] + T[node<<1|1];
}
void Update(int l, int r, int node=1, int s=1, int e=N){
    Push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){ L[node] ^= 1; Push(node, s, e); return; }
    int m = s + e >> 1;
    Update(l, r, node<<1, s, m);
    Update(l, r, node<<1|1, m+1, e);
    T[node] = T[node<<1] + T[node<<1|1];
}
Node Query(int l, int r, int node=1, int s=1, int e=N){
    Push(node, s, e);
    if(r < s || e < l) return Node();
    if(l <= s && e <= r) return T[node];
    int m = s + e >> 1;
    return Query(l, r, node<<1, s, m) + Query(l, r, node<<1|1, m+1, e);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> S; S = "#" + S;
    Init(1, 1, N);
    cin >> Q;
    while(Q--){
        int op, a, b; cin >> op >> a >> b;
        if(op == 1) Update(a, b);
        else{
            auto res = Query(a, b);
            int ans = 0;
            if(res.mn < 0) ans -= res.mn, res.sum -= res.mn;
            ans += res.sum;
            cout << ans + b - a + 1 << "\n";
        }
    }
}