题目链接：
http://codeforces.com/contest/1248/problem/D2
题意：
可以执行一次字符交换的操作
使得操作后的字符串，循环移位并且成功匹配的方案最多
输出最多的方案数和交换的位置
数据范围：
$1\leq n \leq 300 000$
分析：
参考博客：https://www.cnblogs.com/LLTYYC/p/11718968.html
对于一个字符串，求它的循环移位匹配方案数
可以把字符串转换成折线，从0开始，遇到(则加一，遇到）则减一
如果(和)数量不同，明显答案是0，否则，答案是折线y最小值的顶点数量
可以偏移一下，使得最小值为0，那么整体折线向上偏移
如果折线归0，答案加一
那么考虑可以交换一次的情况
先对折线向上偏移
答案是1的数量或者 2的数量加不交换的答案，即，更改最小值为-1，或者增加0的数量，两种操作方案
其中区间1的数量最小值是1，区间2的数量同理
AC代码：
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxn=3e5+7;
int n;
char S[maxn];
int val[maxn];
int main(){
scanf("%d",&n);
scanf("%s",S+1);
int off=0,minn=1e9;
int now=0;
for(int i=1;i<=n;i++){
if(S[i]==')')now--;
else now++;
if(minn>now){
minn=now;
off=i;
}
}
if(now!=0){
printf("0\n1 1\n");
return 0;
}
int ans=0,ansl=1,ansr=1,anss=0;
for(int i=1;i<=n-1;i++){
val[i+1]=val[i];
int v=(off+i-1)%n+1;
if(S[v]==')')val[i+1]--;
else val[i+1]++;
if(val[i]==0)ans++;
//cout<<val[i]<<" ";
}
// coutMM
anss=ans;
for(int i=1;i<=n+1;i++){
if(val[i]==2){
int en=i+1,tem=1;
while(val[en]>=2){
if(val[en]==2)tem++;
en++;
}
if(tem+anss>ans){
ans=tem+anss;
ansl=(i+off-2+n)%n+1;
ansr=(en+off-2+n)%n+1;
}
i=en;
}
}
for(int i=1;i<=n+1;i++){
//cout<<val[i]<<" ";
if(val[i]==1){
int en=i+1,tem=1;
while(val[en]>=1){
if(val[en]==1)tem++;
en++;
}
if(tem>ans){
ans=tem;
ansl=(i+off-2+n)%n+1;
ansr=(en+off-2+n)%n+1;
}
i=en;
}
} printf("%d\n%d %d\n",ans,ansl,ansr);
return 0;
}