题目传送门

题目大意：

给出一个括号串，任意交换两个位置，对串进行循环排列，能得到最多的完全匹配上串有多少个
例如对，循环位移两位后变为，也是一个完全匹配的串

做法：

1.对于一个括号串，可以用栈的方式进行匹配，匹配完后栈为空则串可以被完全匹配
2.思考用栈匹配的过程，若栈底出现了一个')'，那么这个串无论如何无法被匹配
3.考虑将赋值为，赋值为，若前缀和中出现了负数，则串显然无法被匹配，因为相当于多出了一些在这个前缀中无法被匹配，如果在前面没法被匹配，则在后面更加无法被匹配
4.若前缀和始终大于等于并且总和为，则该串可以被完全匹配。自己思考一下为什么。
对于这题，首先可以判断总和是否为,非直接输出
5.对于总和为的情况，考虑怎么移动可以使得每个前缀都
6.去掉一个前缀，设去掉的前缀的前缀和为则对后面的串来说相当于每个前缀，若去掉的前缀为负数，则相当于对后面每个数加上了一个值
7.显然，减去原串中的最小值就可以使得后面每个前缀都
8.当把去掉的前缀放到最后，相当于对这个前缀中的每一个值,显然此时最小值相当于加上了变成了0，而其他点也都了，
9.所以结论就是将前缀的最小值移动到后面就可以得到一个完全匹配的串，答案就是最小值的个数
10.寻找个数是的，再枚举一下交换，最终复杂度为

hard version做法：

0.记最小值为
1.对于交换两个位置来说，相当于交换了两个权值，我们的目标是使得交换后前缀和的最小值出现的次数最多
2.如果交换的两个数相同，显然对前缀无影响，如果交换和，那么相当于对两个位置所夹位置区间内每个前缀,显然不会增加答案个数，所以枚举与交换
3.如果存在一个最小值点被包含在交换的两个端点内，则最小值，答案显然小于等于原答案，所以交换的两个端点不可以跨过原先的最小值
4.要想答案变大，有两种可能，出现一个新的最小值，他的数量比原先的最小值多；或者增加现有最小值的数量。因为交换的操作是对区间,所以对每个操作区间枚举有多少和即可

AC代码

// #pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 3e5 + 10;
char s[maxn], ss[maxn];
int pre[maxn];
int main()
{
    int n;
    read(n);
    scanf("%s", s + 1);
    int cnt = 0;
    int minv = inf;
    int pos = 1;
    for (int i = 1; i <= n; ++i)
    {
        if(s[i]=='(')
            ++cnt;
        else
            --cnt;
        if (cnt < minv)
        {
            minv=cnt;
            pos = i;
        }
    }
    if (cnt)
    {
        puts("0\n1 1");
        return 0;
    }
    for (int i = 1; i <= n; ++i)
    {
        ss[i] = s[(pos + i - 1) % n + 1];
    }
    ss[n + 1] = 0;
    vector<int> p[2];
    p[0].push_back(0);
    int res = 0, l = 1, r = 1;
    cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        pre[i] = pre[i - 1] + (ss[i] == '(' ? 1 : -1);
        if (pre[i] == 0)
        {
            p[0].pb(i);
            ++cnt;
        }
        if (pre[i] == 1)
            p[1].pb(i);
    }
    res = cnt;
    int lt, rt;
    for (int i = 1; i < p[0].size(); ++i)
    {
        lt = p[0][i - 1] + 1, rt = p[0][i];
        int ret = 0;
        for (int j = lt; j <= rt; ++j)
        {
            ret += pre[j] == 1;
        }
        if (ret > res)
        {
            res = ret;
            l = lt;
            r = rt;
        }
    }
    for (int i = 1; i < p[1].size(); ++i)
    {
        int ret = cnt;
        lt = p[1][i - 1] + 1, rt = p[1][i];
        if (pre[lt] == 0)
            continue;
        for (int j = lt; j <= rt; ++j)
        {
            ret += pre[j] == 2;
        }
        if (ret > res)
        {
            res = ret;
            l = lt;
            r = rt;
        }
    }
    printf("%d\n", res);
    printf("%d %d\n", (l + pos - 1 + n) % n + 1, (r + pos - 1 + n) % n + 1);
}