まず、長さ \(M\) の括弧列 \(S\) が正しい括弧列であるかを判定する方法を考えます。\(S\) の ( を \(+1\) 、) を \(-1\) に置き換えた数列を \(A=(A_1,A_2,\ldots,A_M)\) とし、\(A\) の前から累積和をとった数列を \(B=(B_0,B_1,\ldots,B_M)\) とします。例えば、\(S=\)(()) のとき \(A=(1,1,-1,-1)\) 、\(B=(0,1,2,1,0)\) です。このとき、\(S\) が正しい括弧列であるための条件は以下です。

\(B_M=0\) であり、かつ \(B\) の要素の最小値が \(0\) である

元の問題でのクエリは区間に対するクエリなので、セグメント木を用いることを考えます。セグメント木の各ノードには対応する連続部分文字列に対する \(B\) の要素の最小値と \(B_M\) の値を管理しておきます。これらの情報から \(2\) つの区間を \(O(1)\) でマージすることができるので、一点更新区間取得のセグメント木を用いることでこの問題が解けました。

別解として、\(B\) 自体をセグ木で管理すると、区間加算区間最小値取得のセグメント木を用いることで解くことも可能です。

実装例 (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;
        }
    }
}

実装例（C++）（別解）

#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;
        }
    }
}