Code : Invertible Bracket Sequences

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

void solve(string &str) {
    int n = str.length();

    // All prefix sum computation is done on the inverse of the string.
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = (str[i] == '(') ? -1 : 1;
    }

    vector<int> pref(n);
    map<int, vector<int>> psum_to_index;
    for (int i = 0; i < n; i++) {
        pref[i] = a[i] + (i ? pref[i - 1] : 0);
        psum_to_index[pref[i]].push_back(i);
    }

    // There are 2 conditions for a substring to be balanced parentheses.
    // 1. Subarray sum is zero.
    // 2. Non-inverse prefix sum till L - 1 + Inverse prefsum[L...R] >= 0
    //
    // safe[l] = r means that any substring that starts at index 'l' and ends
    // at index <= r will always satisfy condition 2. If no such index exists,
    // it is set to -1.

    vector<int> safe(n, -1);
    int offset = 0;
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            int sum = pref[r] - (l ? pref[l - 1] : 0);
            if (offset + sum < 0) {
                break;
            }
            safe[l] = r;
        }
        offset += (str[l] == '(') ? 1 : -1;
    }

    long long ans = 0;
    for (int l = 0; l < n; l++) {
        if (safe[l] == -1) {
            continue;
        }

        // To satisfy condition 1, we look for all safe indices which will
        // produce a subarray sum of zero.
        int need_psum = l ? pref[l - 1] : 0;
        auto &vec = psum_to_index[need_psum];

        ans += upper_bound(vec.begin(), vec.end(), safe[l]) -
               lower_bound(vec.begin(), vec.end(), l);
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        string str;
        cin >> str;
        solve(str);
    }
    return 0;
}

#include <atcoder/segtree>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

int op(int a, int b) { return min(a, b); }

int e() { return 1e9; }

void solve(string &str) {
    int n = str.length();

    // All prefix sum computation is done on the inverse of the string.
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = (str[i] == '(') ? -1 : 1;
    }

    vector<int> pref(n);
    map<int, vector<int>> psum_to_index;
    for (int i = 0; i < n; i++) {
        pref[i] = a[i] + (i ? pref[i - 1] : 0);
        psum_to_index[pref[i]].push_back(i);
    }

    // There are 2 conditions for a substring to be balanced parentheses.
    // 1. Subarray sum is zero.
    // 2. All prefix sums of the subarray are non-negative.
    //
    // safe[l] = r means that any substring that starts at index 'l' and ends
    // at index <= r will always satisfy condition 2. If no such index exists,
    // it is set to -1.

    segtree<int, op, e> st(pref);
    vector<int> safe(n, -1);
    int orig_pref_sum = 0;
    for (int l = 0; l < n; l++) {
        int low = l, high = n - 1;
        while (low <= high) {
            int mid = (low + high) / 2;

            // Adding +1 because atcoder's segtree has [close, open) range.
            int mn = st.prod(l, mid + 1);
            int sum = mn - (l ? pref[l - 1] : 0);
            if (orig_pref_sum + sum < 0) {
                high = mid - 1;
            } else {
                low = mid + 1;
                safe[l] = mid;
            }
        }
        orig_pref_sum += (str[l] == '(') ? 1 : -1;
    }

    long long ans = 0;
    for (int l = 0; l < n; l++) {
        if (safe[l] == -1) {
            continue;
        }

        // To satisfy condition 1, we look for all safe indices which will
        // produce a subarray sum of zero.
        int need_psum = l ? pref[l - 1] : 0;
        auto &vec = psum_to_index[need_psum];

        ans += upper_bound(vec.begin(), vec.end(), safe[l]) -
               lower_bound(vec.begin(), vec.end(), l);
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        string str;
        cin >> str;
        solve(str);
    }
    return 0;
}

#include <atcoder/segtree>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

int op(int a, int b) { return min(a, b); }

int e() { return 1e9; }

int target;
bool f(int v) { return v >= target; }

void solve(string &str) {
    int n = str.length();

    // All prefix sum computation is done on the inverse of the string.
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = (str[i] == '(') ? -1 : 1;
    }

    vector<int> pref(n);
    map<int, vector<int>> psum_to_index;
    for (int i = 0; i < n; i++) {
        pref[i] = a[i] + (i ? pref[i - 1] : 0);
        psum_to_index[pref[i]].push_back(i);
    }

    // There are 2 conditions for a substring to be balanced parentheses.
    // 1. Subarray sum is zero.
    // 2. All prefix sums of the subarray are non-negative.
    //
    // safe[l] = r means that any substring that starts at index 'l' and ends
    // at index <= r will always satisfy condition 2. If no such index exists,
    // it is set to -1.

    segtree<int, op, e> st(pref);
    vector<int> safe(n, -1);
    int offset = 0;
    for (int l = 0; l < n; l++) {
        // Safe indices have the form
        // s, s, s, ..., s, u, u, u, .... u
        // s --> safe and u --> unsafe.
        //
        // Let's find out the rightmost unsafe index via binary search on
        // segtree.
        // An index is safe if offset + subarray_sum >= 0
        // offset + pref[r] - pref[l - 1] >= 0
        // pref[r] >= pref[l - 1] - offset
        target = (l ? pref[l - 1] : 0) - offset;
        int unsafe = st.max_right<f>(l);
        unsafe--;
        if (l <= unsafe) {
            safe[l] = unsafe;
        }
        offset += (str[l] == '(') ? 1 : -1;
    }

    long long ans = 0;
    for (int l = 0; l < n; l++) {
        if (safe[l] == -1) {
            continue;
        }

        // To satisfy condition 1, we look for all safe indices which will
        // produce a subarray sum of zero.
        int need_psum = l ? pref[l - 1] : 0;
        auto &vec = psum_to_index[need_psum];

        ans += upper_bound(vec.begin(), vec.end(), safe[l]) -
               lower_bound(vec.begin(), vec.end(), l);
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        string str;
        cin >> str;
        solve(str);
    }
    return 0;
}