First we consider how to determine if a string \(S\) of length \(M\) is a correct parenthesis sequence. Let \(A=(A_1,A_2,\ldots,A_M)\) be the sequence of integers obtained by replacing ( in \(S\) with \(+1\) and ) with \(-1\)m and \(B=(B_0,B_1,\ldots,B_M)\) be the cumulative sums of the prefixes. For example, if \(S=\)(()), then \(A=(1,1,-1,-1)\) and \(B=(0,1,2,1,0)\). Then, \(S\) is a correct parenthesis sequence if and only if:

\(B_M=0\) and the minimum element of \(B\) is \(0\).

The queries in the original problem are queries for segments, so we consider using a segment tree. Each node of the segment tree will manage the minimum element of \(B\) and \(B_M\) for the corresponding to contiguous substring. From these information, two segments can be merged in an \(O(1)\) time, so the problem can be solved using a segment tree capable of one-element updates and contiguous-elements derivations.

Alternatively, we can manage \(B\) it self with a segment tree, using a segment tree capable of contiguous-elements addition and contiguous-elements minimum value derivations.

Sample code (C++)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

pair<int, int> op(pair<int, int> a,pair<int, int> b){
    return make_pair(min(a.first, a.second + b.first), a.second + b.second);
}
pair<int, int> e(){
    return make_pair(0, 0);
}

int main(){
    int n, q; cin >> n >> q;
    string s; cin >> s;
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; i++){
        if(s[i] == '(') v[i] = make_pair(0, 1);
        else v[i] = make_pair(-1, -1);
    }
    segtree<pair<int, int>, op, e> seg(v);
    for(int i = 0; i < q; i++){
        int t, l, r; cin >> t >> l >> r; l--; r--;
        if(t == 1){
            swap(v[l], v[r]);
            seg.set(l, v[l]);
            seg.set(r, v[r]);
        }
        else{
            if(seg.prod(l, r + 1) == make_pair(0, 0)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}

Sample code (C++) (Alternative solution)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

int op(int a, int b){ return min(a, b); }
int e(){ return 1001001001; }
int mapping(int f, int x){ return f+x; }
int composition(int f, int g){ return f+g; }
int id(){ return 0; }

int main(){
    int n, q; cin >> n >> q;
    string s; cin >> s;
    vector<int> v(n + 1);
    for(int i = 0; i < n; i++){
        if(s[i] == '(') v[i + 1] = v[i] + 1;
        else v[i + 1] = v[i] - 1;
    }
    lazy_segtree<int, op, e, int, mapping, composition, id> seg(v);
    for(int i = 0; i < q; i++){
        int t, l, r; cin >> t >> l >> r;
        if(t == 1){
            if(s[l - 1] == '(' && s[r - 1] == ')') seg.apply(l, r, -2);
            if(s[l - 1] == ')' && s[r - 1] == '(') seg.apply(l, r, 2);
            swap(s[l - 1], s[r - 1]);
        }
        else{
            if(seg.prod(l - 1, r + 1) == seg.get(l - 1) && seg.get(l - 1) == seg.get(r)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}