Bring Balance

题目描述

Alina 有一个长度为 \(2n\) 的括号序列 \(s\)，由 \(n\) 个左括号 ( 和 \(n\) 个右括号 ) 组成。她想把这个括号序列变成一个平衡括号序列。

平衡括号序列定义为：能通过插入字符 + 和 1 使之成为合法数学表达式的序列。例如，序列 (())()、() 和 (()(())) 是平衡的，而 )(、(() 和 (()))( 就不是的。

在一次操作中，她可以反转 \(s\) 的任意子串。

请求出最少几次操作可将 \(s\) 转换为平衡括号序列。可以证明，这总是能在 \(n\) 次操作中完成。

\(n\le 10^5\)。

Solution

考虑将括号序列转化成为折线图，( 看作是 \((+1,+1)\)，) 看作是 \((+1,-1)\)，那么考虑一次翻转在折线图上有什么性质。假设翻转的区间为 \([l,r]\)，折线图在 \(x=l\) 处的坐标为 \((l,a)\)，在 \(x=r\) 处的坐标为 \((r,b)\)，那么这次翻转相当于是将 \([l,r]\) 之间的所有点关于 \((\dfrac{l+r}{2},\dfrac{a+b}{2})\) 中心对称。问题变成如何翻转使得这个折线图所有部分都在 \(x\) 轴之上。

观察发现，最多只需要两次操作就可以使得原序列符合条件。一个点 \((c,d)\) 关于 \((\dfrac{l+r}2,\dfrac{a+b}2)\) 会中心对称到 \((l+r-c,a+b-d)\)。设全局最大值的位置为 \(p\)，那么翻转 \([1,p)\) 和 \((p,2n]\) 一定是一个合法解。对于 \([1,p)\) 中的点 \((c,d)\)，有 \(d\le y_p\)，也就是说 \(a+y_p-d=y_p-d\ge 0\)，也就意味着这样翻转后，\([1,p)\) 中的所有点都将在 \(x\) 轴之上。\((p,2n]\) 同理。

那么只需要判断是否存在 \(1\) 次操作或者原本就是合法序列的情况。不操作的情况显然好做。对于只需要一次操作的，先找到第一个和最后一个 \(y<0\) 的点 \(p_1,p_2\)，那么翻转的区间 \([L,R]\) 一定有 \(L\le p_1,R\ge p_2\)，并且 \(L,R\) 选的位置 \(y\) 越大越好。那么直接找 \([1,p_1)\) 和 \((p_2,2n]\) 中的最大值出现的位置作为 \(L,R\)，然后暴力验证即可。

时间复杂度 \(\mathcal O(n)\)。

Code

// Cirno is not baka!
#include <bits/stdc++.h>
#define For(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define Rof(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define FILE(filename) { \
    freopen(#filename ".in", "r", stdin); \
    freopen(#filename ".out", "w", stdout); \
}
#define All(x) x.begin(), x.end()
#define rAll(x) x.rbegin(), x.rend()
#define pii pair<int, int>
#define fi first
#define se second
#define i64 long long
#define mkp make_pair
// #define int long long
#define epb emplace_back
#define pb push_back
using namespace std;

const int _N = 2e5 + 5, mod = 1e9 + 7, inf = 1e9;
template<typename T> void Max(T &x, T y) {x = max(x, y);}
template<typename T> void Min(T &x, T y) {x = min(x, y);}

namespace BakaCirno {
    int N;
    int A[_N], B[_N];
    bool Check0() {
        return *min_element(A + 1, A + 2 * N + 1) >= 0;
    }
    bool Check1() {
        int p1 = 2 * N + 1, p2 = 0;
        For(i, 1, 2 * N) if (A[i] < 0)
            Min(p1, i), Max(p2, i);
        int l = max_element(A, A + p1 + 1) - A + 1;
        int r = max_element(A + p2 + 1, A + 2 * N + 1) - A;
        reverse(B + l, B + r + 1);
        partial_sum(B + 1, B + 2 * N + 1, B + 1);
        if (*min_element(B + 1, B + 2 * N + 1) >= 0) {
            cout << 1 << '\n';
            cout << l << ' ' << r << '\n';
            return 1;
        }
        return 0;
    }
    void _() {
        cin >> N;
        For(i, 1, 2 * N) {
            char c; cin >> c;
            B[i] = (c == '(' ? 1 : -1);
            A[i] = B[i] + A[i - 1];
        }
        if (Check0()) return cout << 0 << '\n', void();
        if (Check1()) return ;
        cout << 2 << '\n';
        int p = max_element(A + 1, A + 2 * N + 1) - A;
        cout << 1 << ' ' << p - 1 << '\n';
        cout << p + 1 << ' ' << 2 * N << '\n';
    }
}

signed main() {
    // FILE(test);
    cin.tie(0)->sync_with_stdio(0); int T = 1;
    cin >> T;
    while (T--) BakaCirno::_();
    // fout.flush();
}