CF1685C Bring Balance。

如果这是 ccf 的考试，看大样例大概率能看出性质。

整体的思路：括号匹配问题先转化成前缀和，然后分析问题可以画图，就画前缀和的折线图，然后分析翻转有什么影响。

合法的序列需要是每一个前缀和都大于等于 00 的，所以我们可以转化成前缀和做。

观察到性质：翻转一个区间之后最低的点一定是原来最高的点，所以我们只需要让原来最高的点翻转过后不小于 00。

然后充分发扬人类智慧，对于最高的点 xx，翻转 [1,x],[x+1,2n][1,x],[x+1,2n] 一定合法，所以最多需要两次。

那还有没有一次的情况呢？

设需要翻转 l,rl,r。我们考虑 L,RL,R 表示最左边和最右边的负数，然后我们从 [1,L][1,L] 和 [R,2n][R,2n] 选 l,rl,r。我们需要保证对于每一个 ii，sl−1+sr−si≥0s_{l-1}+s_r-s_i \ge 0，于是可以贪心，分别选择 [1,L−1][1,L-1] 和 [R,2n][R,2n] 中最大的两个端点作为 l,rl,r，然后判断这样选合不合法。

C++
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
char c[200010];
int a[200010];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n*2;i++)cin>>c[i];
		for(int i=1;i<=n*2;i++)a[i]=a[i-1]+(c[i]=='('?1:-1);
		int pd=1;
		for(int i=1;i<=n*2;i++)if(a[i]<0){pd=0;break;}
		if(pd){cout<<0<<'\n';continue;}
		int l=0,r=0;
		int p=0;
		a[0]=0;
		for(int i=1;i<=n*2;i++){
			if(a[i]>=a[p]||!p)p=i;
			if(a[i]<0){
				if(!l)l=i;
				r=i;
			}
		}
		int pa=0,pb=0;
		for(int i=1;i<l;i++)if(a[i]>=a[pa]||!p)pa=i;
		for(int i=r;i<=n*2;i++)if(a[i]>=a[pb]||!p)pb=i;
		int ok=1;
//		cout<<l<<' '<<r<<' '<<pa<<' '<<pb<<endl;
		for(int i=pa+1;i<=pb;i++){
			if(a[pa]+a[pb]-a[i]<0){
				ok=0;
				break;
			}
		}
		
		if(ok){
			cout<<1<<'\n';
			cout<<pa+1<<' '<<pb<<endl;
		}else{
			cout<<2<<'\n';
			cout<<1<<' '<<p<<'\n'<<p+1<<' '<<n*2<<'\n';
		}
	}
	
	
	return 0;
}