CF1685C Bring Balance 题解

题意：

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

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

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

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

输入格式：

本题有多组数据。

第一行一个整数 \(t\)（\(1 \le t \le 2 \cdot 10^4\)），表示数据组数。

每组数据格式如下：

第一行一个整数 \(n\)（\(1 \le n \le 10^5\)），含义如上所述。

第二行为一个长度为 \(2n\) 的括号序列，由 \(n\) 个左括号 ( 和 \(n\) 个右括号 ) 组成。

在一个测试点中，所有 \(n\) 的总和不超过 \(2\cdot 10^5\)。

输出格式：

对于每一组数据，第一行输出一个整数 \(k~(0 \le k \le n)\)，表示最少 \(k\) 次操作可将 \(s\) 转换为平衡括号序列。

在接下来的 \(k\) 行中，第 \(i\) 行有两个整数 \(l_i,r_i~(1 \le l_i \le r_i \le 2n)\)，表示在第 \(i\) 次操作中，Alina 会反转子串 \(s_{l}s_{l+1}\cdots s_{r-1}s_{r}\)（序列从 \(1\) 开始编号）。

如果有多种方式将原序列转换为平衡序列，输出其中任意一种即可。

令左括号为 \(1\) ，右括号为 \(-1\) ，则括号串合法当且仅当任意位置的前缀和非负。

由于本题左括号和右括号数量相等，所以 \(S_0\) 和 \(S_{2n}\) 均为 \(0\) ，考虑利用这个性质。

如果我们把整个前缀和看作坐标轴上的点，连线后可得一张折线图

注意到一次操作区间 \([l,r]\) 后，相当于把 \([l,r]\) 间的曲线中心对称后接在 \(l\) 上。

于是我们找到 \(a_i\) 最大的那个点，记为 \(p\) ，翻转 \([1,p]\) 和 \([p+1,n]\) 即可使原串合法。

取最大的 \(a_i\) 是为了保证接上去以后不会跑到坐标轴以下。

那么是否有仅需要操作一次的情况呢？答案是有的，比如下面这种。

如果按照我们刚才的方法，就会发现左侧根本不需要翻转。

显然，这种情况是左侧没有负数情况导致的。相对的，右侧也可能有这种情况。

考虑找到左侧和右侧最远的 \(-1\) ，记为 \(l,r\) ，那么我们要翻转的区间 \([L+1,R]\) 满足： \[ \begin{cases} L \in [1, l),\, R \in (r,n] \\[6pt] a_{L} = \max\{a_i\mid 0 \le i \le L\} \\[6pt] a_{R} = \max\{a_i \mid R \le i \le 2n\} \end{cases} \] 于是我们实际翻转的就是

需要看那严谨证明的话可以去看下面的参考文献1，不过我觉得没这个直观（~~OI 不需要证明~~）

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(4e5 + 15))

char s[N]; int a[N];
void solve()
{
    int n; cin >> n >> (s + 1); n <<= 1; bool ok = true;
    rep(i, 1, n) { a[i] = a[i - 1] + (s[i] == '(' ? 1 : -1); if(a[i] < 0) ok = false; }
    if(ok) return cout << "0\n", void(0);
    ok = true; int l = 0, r = 0;
    rep(i, 1, n) if(a[i] < 0) { l = i; break; }
    Rep(i, n, 1) if(a[i] < 0) { r = i; break; }
    int mx = -INF, mx1 = -INF, mx2 = -INF, L = 0, R = 0, p = 0;
    rep(i, 0, l) if(a[i] > mx1) { mx1 = a[i]; L = i; }
    rep(i, r, n) if(a[i] > mx2) { mx2 = a[i]; R = i; }
    rep(i, L, R) if(mx1 + mx2 - a[i] < 0) { ok = false; break; }
    if(ok) { cout << "1\n" << L + 1 << ' ' << R << '\n'; return; }
    rep(i, 1, n) if(a[i] > mx) { mx = a[i], p = i; }
    cout << "2\n" << "1 " << p << '\n' << p + 1 << ' ' << n << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}