Codeforces Round #594 (Div. 2 )D2 The World Is Just a Programming Task (Hard Version) 思维

题目链接
题意：给一个长度为n的括号序列，你可以选择其中两个进行交换，问怎样交换可以使该括号序列的循环位置的个数最大
循环位置i可以理解为 把前i个字符放到最后面之后能使这个括号序列变成合法序列
例：（）（（）（））（） 循环位置有 2,8,10；

首先，如果一个序列的左右括号数量不相等。那他就没有循环位置，特判掉就可以。
那显然一个数量相等的括号序列一个可以通过位移 改变成一个合法的括号序列。恰巧，操作这个合法序列的括号位置和操作原来序列的括号位置得到的答案使一样的。（）

那么接下来就很简单了，我们考虑把括号分成 一级括号，二级括号，三级括号…；
那如果我们交换一级括号的左右括号，这时得到的答案就是一级括号里二级括号的数量加一
画个图会清晰很多
以此类推交换二级括号和三级括号的答案
至于一级和二级或者一级和三级之间交换画个图也可以看出来

#include<bits/stdc++.h>

typedef long long int ll;
using namespace std;
const int maxn=3e5+5;
int level[maxn*2],num[maxn*2],par[maxn*2];
char s[maxn*2];
stack<int>stk;
int main()
{
     ())(()
     
	 int n,cnt=0;
	 scanf("%d",&n);
	 scanf("%s",s+1);
	 for(int i=1;i<=n;i++){
        if(stk.empty()) stk.push(i);
        else {
            int c=stk.top();
            if(s[i]==')'&&s[c]=='(') stk.pop();
            else stk.push(i);
        }
        s[i+n]=s[i];
        cnt=cnt+((s[i]=='(')?(1):(-1));//cout<<cnt<<endl;
	 }
	 if(cnt) return 0&printf("0\n1 1\n");
	 int j=1;
	 while(!stk.empty()){
        int c=stk.top();
        if(s[c]==')') break;
        stk.pop();
        j=c;
	 }
	 for(int i=1;i<=n*2;i++) level[i]=-1,num[i]=0;
	 while(!stk.empty()) stk.pop();
	 for(int i=j;i<=j+n-1;i++){
        if(stk.empty()) {
            stk.push(i);
            level[i]=1;
            cnt++;
        }
        else {
            int c=stk.top();
            if(s[i]==')'&&s[c]=='(') {
                stk.pop();
                par[c]=i;
            }
            else {
                stk.push(i);
                level[i]=stk.size();
            }
        }
	 }

	 int i=j;
	 while(i<=j+n-1){
        if(level[i]==1){
            int r=par[i],k=i;
            while(i<r){
                if(level[i]==2) num[k]++;
                i++;
            }
        }
        i++;
	 }

	 i=j;
	 while(i<=j+n-1){
        if(level[i]==2){
            int r=par[i],k=i;
            while(i<r){
                if(level[i]==3) num[k]++;
                i++;
            }
        }
        i++;
	 }

	 int ans=0,l,r;
	 for(int i=j;i<=j+n-1;i++){
        if(level[i]==1){
            if(ans<(num[i]+1)){
                ans=num[i]+1;
                l=i%n;r=par[i]%n;
            }
        }
        else if(level[i]==2){
            //ans=max(ans,cnt+num[i]+1);
            if(ans<(cnt+num[i]+1)){
                ans=cnt+num[i]+1;
                l=i%n;r=par[i]%n;
            }
        }
	 }
	 if(ans<cnt) ans=cnt,l=1,r=1;

	 if(l==0) l=n;if(r==0) r=n;
	 printf("%d\n%d %d\n",ans,l,r);
}