올바른 괄호 세그먼트 트리

구간이 올바른 괄호문자열인지 판정하는 쿼리,
구간 문자 뒤집기 '(' <-> ')' 업데이트 쿼리 모두를 O(log N)에 처리하는 세그먼트 트리

C. Sereja and Brackets : 업데이트 X

17407 괄호 문자열과 쿼리 : 점 업데이트

19851 버거운 버거: 구간 업데이트

일반적으로 사용하는 세그 트리의 노드의 종류는 2가지다. 
레이지 값은 별도로 저장한다고 가정한다.

1. 구간합과 최소,최대 저장

앞서 '('를 1, ')'를 -1로 모델링했을 때
[a,b] 부분문자열이 올바른 괄호문자열일 조건은
$Sum([a,b]) = 0$ 이고 $Min(Sum([a,i])) >= 0$임을 언급했다.

이를 이용하기 위해 노드에 구간합과 최솟값을 저장한다 만약 구간의 문자를 뒤집을 경우 최솟값이 구간합의 최댓값이 되기 때문에 최댓값 또한 같이 저장해준다.

두 노드를 합치는 방법은 다음과 같다.
Node{ int sum, mn, mx }에 대해
sum = L.sum + R.sum
mn = min(L.mn, L.sum+R.mn)
mx = max(L.mx, L.sum+R.mx)

어떤 문자열을 올바른 괄호문자열로 만들기 위해 괄호를 추가할 때 최소 길이는
기존 길이 + (-mn) + (sum + (-mn))이 된다.
-mn은 왼쪽에 추가해야할 괄호의 개수, sum-mn은 오른쪽에 추가해야할 괄호의 개수다.

2. 올바른 괄호문자열을 만들기 위해 왼쪽, 오른쪽에 더 넣어야 하는 괄호 개수 저장

가령 ) ( ) ( ) ) ) (과 같은 문자열에서 이미 올바른 괄호문자열인 부분을 제거하면
) ) ) (이 된다. 왼쪽에 추가해야할 '(' 의 개수는 3, 오른쪽에 추가해야할 ')'의 개수는 1이다.

이렇게 저장했을 때 장점은 노드의 합성이 직관적이라는 것.
두 노드를 합칠 때 L.right와 R.left가 상쇄되는 것을 이해해보자
Node{ left, right }로 두면
left = L.left + max(0, R.left - L.right)
right = R.right + max(0,L.right - R.left)

노드를 뒤집었을 때 이를 처리하는 방법은 그냥 미리 뒤집었다고 생각하고 left, right를 계속 들고 다니는 것이다.
즉 Rleft, Rright를 들고다니면서 노드를 합칠 때 Rleft, Rright들끼리 합쳐준다.

문자열을 뒤집으면 Rleft와 left를 swap, Rright와 right를 swap하면 된다.

3. 구현

1번, 2번 모두 편하지만 
실제로 구현할 때는 1번이 더 쉽게 짤 수 있을 것으로 느껴진다.

버거운 버거 문제를 풀고 sebinkim님의 풀이를 봤는데
update와 구간 적합성 판정, 2개의 쿼리를 하나의 함수를 통해 처리하는 것을 보고 감명 받았다.

Node 구조체를 따로 만들어서 lazy 값과 합치는 내부 메소드를 구현해놓는 것이 매우 편하다!

#pragma GCC optimize("Ofast")
//Always Do Your Best Ku!
#include<bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define nl '\n'
#define sp ' '
using ll = long long;
using pii = pair<int,int>;
const int inf = 1e9;
#define dbg(X) cerr<<#X<<'='<<X<<nl
#define GET_TC 0

struct Node{
    int l[2]{},r[2]{};
    bool lz=0;
    Node(){}
    Node(char c){l[1]=r[0]=1;if(c==')')flip();}
    void flip(){swap(l[0],l[1]); swap(r[0],r[1]);}
    void merge(const Node&a,const Node&b){
        for(int i=0;i<2;i++){
            l[i] = a.l[i] + max(0,b.l[i]-a.r[i]);
            r[i] = b.r[i] + max(0,a.r[i]-b.l[i]);
        }
        if(lz) flip();
    }
}; 
struct Seg{
    vector<Node> tree; int b = 1; 
    Seg(int n = 1){
        while(b<n) b<<=1;
        tree.assign(b<<1,Node());
    }
    void init(int p,int s,int e,string&str){
        if(s==e){
            tree[p] = Node(str[s-1]);
            return;
        }
        init(p<<1,s,s+e>>1,str); init(p<<1|1,s+e+2>>1,e,str);
        tree[p].merge(tree[p<<1],tree[p<<1|1]);
    }
    Node query(int p,int s,int e,int l,int r,int mode){
        Node res;
        if(l<=s && e<=r){
            if(mode==1) tree[p].lz ^= 1, tree[p].flip();
            else res = tree[p];
        }else if(!(e<l || r<s)){
            Node L = query(p<<1,s,s+e>>1,l,r,mode);
            Node R = query(p<<1|1,s+e+2>>1,e,l,r,mode);
            if(mode==1) tree[p].merge(tree[p<<1],tree[p<<1|1]);
            else{
                res.merge(L,R);
                if(tree[p].lz) res.flip(); //[s,e]와 연관된 부분만 res에 들어가 있으므로
            }
        }
        return res;
    }
};
void solve(int TC){
    int n,q; string s; cin>>n>>s>>q;
    Node x;
    Seg f(n);
    f.init(1,1,n,s);
    while(q--){
        int t,a,b; cin>>t>>a>>b;
        x = f.query(1,1,n,a,b,t);
        if(t==2) cout<<(b-a+1+x.l[0]+x.r[0])<<nl;
    }
}

int main(){
    ios::sync_with_stdio(!cin.tie(0));
    int T = 1; if(GET_TC) cin >> T;
    for(int i=1;i<=T;i++) solve(i);
}