#include #include #include #include #include using namespace std; // Structure to hold information about prefix S_i struct PrefixInfo { int id; // Original index (1 to N) of the prefix S_i int len; // Length of the prefix S_i, which is equal to i long long bal; // Balance = count('(') - count(')') in S_i long long min_bal; // Minimum balance over all prefixes of S_i (including the empty prefix with balance 0) long long open_count; // Count of '(' characters in S_i long long close_count; // Count of ')' characters in S_i }; // Global pointer to the input string S to avoid copying it multiple times const string* global_S_ptr; /** * @brief Comparison function for sorting prefixes. * * This function defines the sorting order for the prefixes S_1, ..., S_N. * The goal is to find an order of concatenation T = S_{\pi(1)}...S_{\pi(N)} * such that the minimum prefix balance of T is maximized. This is known to help * in problems related to balanced parentheses formation. * * The comparison logic is based on checking which order (A then B, or B then A) * yields a better (higher) minimum prefix balance for the combined string AB or BA. * A prefix X comes before prefix Y if the minimum balance achieved by concatenating X then Y * is greater than or equal to the minimum balance achieved by concatenating Y then X. * Specifically, X precedes Y if min(minB(X), bal(X) + minB(Y)) >= min(minB(Y), bal(Y) + minB(X)). * * Tie-breaking rules are applied if the primary comparison yields equality. * First, based on balance (higher balance preferred). * Second, based on original index (lower index preferred for stability). */ bool comparePrefixes(const PrefixInfo& a, const PrefixInfo& b) { // Calculate the minimum balance if A is concatenated before B long long min_a_b = min(a.min_bal, a.bal + b.min_bal); // Calculate the minimum balance if B is concatenated before A long long min_b_a = min(b.min_bal, b.bal + a.min_bal); // Prefer the order that results in a higher minimum balance if (min_a_b != min_b_a) { return min_a_b > min_b_a; } // Tie-breaking rule 1: Prefer prefix with higher balance. This is a heuristic choice. if (a.bal != b.bal) { return a.bal > b.bal; } // Tie-breaking rule 2: Use original index to ensure stability and deterministic order. return a.id < b.id; } /** * @brief Computes matches and final open count for processing prefix S[0...len-1] * starting with an initial open parenthesis count `k`. * * This function simulates the standard greedy algorithm for finding the length * of the longest balanced parenthesis subsequence on the given prefix. * * @param len The length of the prefix S_i to process (which is i). * @param k The initial count of open parentheses before processing this prefix. * @return A pair {matches, final_k}, where `matches` is the number of pairs matched * during processing this prefix, and `final_k` is the open parenthesis count * after processing this prefix. */ pair process_prefix(int len, long long k) { long long current_k = k; // Start with the given open count long long matches = 0; // Initialize matches count for this prefix const string& S = *global_S_ptr; // Access the global input string S // Iterate through the characters of the prefix S[0...len-1] for (int i = 0; i < len; ++i) { if (S[i] == '(') { // Increment open count for '(' current_k++; } else { // S[i] == ')' // If there's an open parenthesis available, match it if (current_k > 0) { current_k--; // Decrease open count matches++; // Increment matched pairs count } // If current_k is 0, this ')' cannot be matched and is ignored. } } // Return the total matches found within this prefix simulation and the final open count return {matches, current_k}; } int main() { // Use fast I/O ios_base::sync_with_stdio(false); cin.tie(NULL); int N; // Length of the string S cin >> N; string S; // The input string of '(' and ')' cin >> S; global_S_ptr = &S; // Set the global pointer to S // Vector to store information about each prefix S_1, ..., S_N vector prefixes(N); long long current_bal = 0; // Running balance long long current_min_bal = 0; // Running minimum balance seen so far long long current_open = 0; // Running count of '(' long long current_close = 0; // Running count of ')' // Calculate properties for each prefix S_i = S[0...i-1] for (int i = 0; i < N; ++i) { // Update counts and balance based on the current character S[i] if (S[i] == '(') { current_bal++; current_open++; } else { current_bal--; current_close++; } // Update the minimum balance encountered up to this point current_min_bal = min(current_min_bal, current_bal); // Store the calculated properties for prefix S_{i+1} prefixes[i].id = i + 1; prefixes[i].len = i + 1; prefixes[i].bal = current_bal; prefixes[i].min_bal = current_min_bal; prefixes[i].open_count = current_open; prefixes[i].close_count = current_close; } // Sort the prefixes based on the custom comparison function `comparePrefixes` sort(prefixes.begin(), prefixes.end(), comparePrefixes); long long total_matches = 0; // Accumulator for total matched pairs across all prefixes long long current_k = 0; // State variable: current count of open parentheses // Iterate through the sorted prefixes and simulate the greedy matching process for (int i = 0; i < N; ++i) { const PrefixInfo& p = prefixes[i]; // Get the current prefix info // Optimization: Check if the current open count `current_k` is sufficient // to handle the potential balance drop within this prefix `p`. // The minimum balance `p.min_bal` represents the largest dip. `p.min_bal` is <= 0. // `-p.min_bal` is the minimum initial `k` needed to ensure `k` never drops below 0 during processing `p`. // If `current_k >= -p.min_bal`, the open count will never reach 0 when a ')' is encountered. // Thus, all ')' characters in `p` will be matched. if (current_k >= -p.min_bal) { // O(1) update: All ')' in this prefix find a match. total_matches += p.close_count; // Update the open count state by adding the balance change of this prefix. current_k += p.bal; } else { // Optimization condition failed. Must simulate the processing of this prefix. // This step takes O(p.len) time. pair result = process_prefix(p.len, current_k); // Add the matches found during the simulation. total_matches += result.first; // Update the open count state to the final count after simulation. current_k = result.second; } } // The final result is twice the total number of matched pairs, as each pair has length 2. cout << total_matches * 2 << endl; return 0; }