Codeforces Round #594 (Div. 1) B. The World Is Just a Programming Task (Hard Version)

这题太妙了，我是看b站qscqesze（搜这个up主）+这个聚聚讲的学会的：https://www.cnblogs.com/LLTYYC/p/11718968.html

写这篇博客不是写题解，只是记录一下，日后比赛前看题解可以看看。题解的话看我上面推的就懂了

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;++i)
#define for1(i,n) for(int i=1;i<=n;++i)
#define IO ios::sync_with_stdio(false);cin.tie(0)
const int maxn = 6e5+5;    
const int inf = 2e9+5;

int a[maxn];

int main(){
    IO;int n;string s;cin>>n>>s;
    forn(i,n){
        a[i+1] = a[i];
        if(s[i] == '(') ++a[i+1]; 
        else --a[i+1];
        a[i+n+1] = a[i+1];
    }

    if(a[n] != 0) return cout << 0 << '
' << 1 <<' '<< 1 <<'
',0;
    int mi = inf,p = 0;
    for1(i,n<<1) if(a[i]<mi) mi = a[i],p = i;
    for1(i,n<<1) a[i] -= mi;
    int ans = 0;
    for(int i = p;i<p+n;++i) if(!a[i]) ++ans;
    //cerr<<p<<'
';
    //for(int i = p;i<=p+n;++i) cerr<< a[i] <<' ';
    //cerr<<'
'<<'
';
    int cnt = ans;
    int num1 = 0,num2 = 0;
    int l = p+1,r = p+1,last2 = p+1,last1 = p+1;
    for(int i = p+1;i<=p+n;++i){
        if(a[i] == 2) ++num2;
        if(a[i] == 1){
            if(ans < num2+cnt){
                ans = num2+cnt;
                l = last2,r = i;
            }
            last2 = i+1;
            num2 = 0;
            ++num1;
        }
        if(a[i] == 0){
            if(ans < num1){
                ans = num1;
                l = last1,r = i;
            }
            num1 = 0;
            last1 = i+1;
        }
    }
    if(l>n) l -= n;
    if(r>n) r -= n;
    if(l>r) swap(l,r);
    cout << ans << '
';
    cout <<l<<' '<<r<<'
';
    return 0;
}