Code : Balanced Substrings

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

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

    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.

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

    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();

    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);
    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 (sum < 0) {
                high = mid - 1;
            } else {
                low = mid + 1;
                safe[l] = mid;
            }
        }
    }

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