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