백준 19851 - 버거운 버거

 

문제 링크 : https://www.acmicpc.net/problem/19851

19851번: 버거운 버거

문제 해석

 

괄호 문자열이 주어진다.

1. 쿼리 1번을 시행시, l ~ r번째 괄호 문자열을 뒤집는다.

2. 쿼리 2번을 시행시, l ~ r번째 괄호 문자열이 올바른 괄호 문자열이 되도록 추가하는 괄호의 최소 갯수를 구한다.

 

문제 풀이

 

"("은 1로, ")"은 -1로 해석해보자.

 

올바른 괄호 문자열이 되려면, 1과 -1로 이루어진 수열 안에서

Minimum prefix sum이 음수가 아니며, 

그 합계가 0을 만족해야한다.

 

만약 올바르지 않은 괄호문자열이 있고 그 minimum prefix sum이 -x, sum이 s라 해보자.

그럼 우리는 괄호문자열의 맨 앞에 x개만큼의 "("괄호를 덮어주고 

s + x개만큼 뒤에 ")"괄호를 덮어주면 가장 짧은 올바른 괄호 문자열이 될 것이다.

 

어떤 구간 l, r에서의 sum과 minimum prefix sum은 금광 세그를 응용하면 logN에 구하게 만들 수 있고, 

l, r 구간을 뒤집는 것은 구간에 -1을 곱해주는 쿼리를 수행하면 된다. (-1을 곱하는 것 때문에 minimum prefix sum 이외에 maximum prefix sum도 저장해 두어야 한다.)

 

코드

 

 
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define uniq(x) sort(all(x)); x.resize(unique(all(x))-x.begin());
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
 
using pii = pair<int, int>;
using ll = long long;
const ll MOD = 1e9 + 7;
const long double PI = acos(-1.0);
 
struct Node {
    ll sum;
    ll mx;
    ll mn;
};
 
class SegmentTree{
public:
    vector<Node> segtree;
    vector<ll> lazy;
    int n;
    
    SegmentTree(int n) {
        segtree.resize(4*n+5, {1,1,1});
        lazy.resize(4*n+5, 1);
        this->n=n;
    }
 
    void propagate(int ns, int ne, int pos) {
        if(lazy[pos]!=1){
            segtree[pos].sum *= lazy[pos];
            segtree[pos].mx *= lazy[pos];
            segtree[pos].mn *= lazy[pos];
            if(segtree[pos].mx < segtree[pos].mn) 
                swap(segtree[pos].mx, segtree[pos].mn);
            if(ns != ne){
                lazy[pos*2] *= lazy[pos];
                lazy[pos*2+1] *= lazy[pos];
            }
            lazy[pos]=1;
        }
    }
    
    void update_(int ns, int ne, int s, int e, int pos, ll value) {
        propagate(ns, ne, pos);
        if(e < ns || s > ne) return;
        if(s <= ns && ne <= e){
            lazy[pos] *= value;
            propagate(ns, ne, pos);
            return;
        }
        ll mid = (ns+ne)/2;
        update_(ns, mid, s, e, pos*2, value);
        update_(mid+1, ne, s, e, pos*2+1, value);
        segtree[pos].sum = segtree[pos*2].sum + segtree[pos*2+1].sum;
        segtree[pos].mx = max(segtree[pos*2].mx, segtree[pos*2].sum + segtree[pos*2+1].mx);
        segtree[pos].mn = min(segtree[pos*2].mn, segtree[pos*2].sum + segtree[pos*2+1].mn);
    }
    
    Node query_(int ns, int ne, int s, int e, int pos) {
        propagate(ns,ne,pos);
        if(e < ns || s > ne) return {0,-LLINF,LLINF};
        if(s <= ns && ne <= e) return segtree[pos];
        int mid=(ns+ne)/2;
        Node ret;
        Node l = query_(ns,mid,s,e,pos*2), r = query_(mid+1,ne,s,e,pos*2+1);
        ret.sum = l.sum + r.sum;
        ret.mx = max(l.mx, l.sum + r.mx);
        ret.mn = min(l.mn, l.sum + r.mn);
           return ret;
    }
    
    void upd(int s, int e, ll value) {
        update_(0,n-1,s,e,1,value);
    }
    
    Node query(int s, int e) {
        return query_(0,n-1,s,e,1);
    }
};
 
int main() {
    IOS;
    int n; cin >> n;
    SegmentTree st(n);
    string s; cin >> s;
    for(int i=0 ; i<n ; i++) {
        if(s[i] == '(') {
            st.upd(i,i,1);
        }
        else {
            st.upd(i,i,-1);
        }
    }
    int q; cin >> q;
    while(q--) {
        int qq; cin >> qq;
        if(qq == 1) {
            int l, r; cin >> l >> r; l--, r--;
            st.upd(l, r, -1);
        } else {
            int l, r; cin >> l >> r; l--, r--;
            Node x = st.query(l, r);
            ll needBurger = 0;
            if(x.mn < 0) {
                needBurger += -x.mn;
                x.sum += -x.mn;
            }
            if(x.sum > 0)
                needBurger += x.sum;
            cout << r-l+1 + needBurger << "\n";
        }
    }
}