题解：CF1239B The World Is Just a Programming Task (Hard Version)
小屹0_0
·
·
题解
又是看不懂别的题解的一天。
首先是一个经典的 trick 就是我们将左括号看成 +1 右括号看成 -1 然后计算前缀和，设为 pre。
当 pre_n \neq 0 的时候直接输出 0 并随机交换两个数字即可。
否则我们考虑这个东西在什么时候是合法的？
为了方便描述我们破环成链。
那么 [l, l + n - 1] 这一段区间合法的条件是？
显然是：
\min\limits_{i = l}^{l + n - 1} pre_i \ge pre_{l - 1}
然后你发现一个很搞笑的事情就是不等号左边的式子是一个固定的值，就是 pre 数组的最小值。
那么要求 pre_{l - 1} \leq \min pre，于是 pre_{l - 1} = \min pre。
于是合法的位置就是所有的 pre 最小下标 +1 处。
现在我们回到原串进行考虑，也就是想要 pre 的最小值出现次数尽可能多应该干什么。
探究交换的本质，其实就是区间 +2 和区间 -2，具体的：
- 若交换的
( 在前 ) 在后则区间 -2，起点是 ( 的位置，终点是 ) 的前一个位置。
- 若交换的
) 在前 ( 在后则区间 +2，起点是 ) 的位置，终点是 ( 的前一个位置。
然后我们为了方便刻画这个最小值，直接任取一个 pre_{l - 1} = \min pre 的位置将这个串断开，将后面的串移到前面。
具体的，我们设 pre_{pos - 1} = \min pre，那么 s \rightarrow s_{pos} s_{pos + 1} \cdots s_{n} s_1 s_2 \cdots s_{pos - 1}。
然后此时我们重新计算前缀和，记为 pre'，有 \min pre' = 0，这是显然的。
我们刻画新串中的操作，这一部分其他题解出现了问题，我们不能显然的认为 +2 是无意义的，尽管确实不优。
为什么这么说呢，我们仔细看看：
首先，新串的 -2 操作。我们注意到若操作的两个字符：
- 都在 [1, n - pos + 1]，则原串也可以类似操作。
- 都在 [n - pos + 2, n]，则原串也可以类似操作。
- 一个在 [1, n - pos + 1]，另一个在 [n - pos + 2, n]。注意到
( 在前 ) 在后，我们希望在新串中还是执行区间 -2，对应原串是前缀 -2 后缀 -2，但是原串中理应是一个区间 +2，然而我们惊奇的发现，前缀 -2 后缀 -2 的效果等同于区间 +2，这一部分其他题解也有欠缺，没有题解提到 -2 有可能会转化为 +2。
其次，新串的 +2 操作。这个操作确实是无意义的，让我们来证明他：
首先我们需要意识到，pre'_1 = 1, pre'_n = 0。
- 我们如果想要改变最小值，那么一定是操作了一个后缀并且包含了所有 pre'_i = 0 的位置，那么这等价于一个前缀 -2。
- 否则不改变最小值的情况下增大一些值显然不会让最小值数量变多。
于是所有 +2 操作要么无意义，要么可以转化为 -2。
于是我们考虑我们会操作使得答案最小值为 -2, -1, 0。
意识到如果是 -2 那么显然 -2 的个数不会超过不操作时 0 的个数，淘汰。
于是我们考虑 -1, 0 的情况。
$0$ 就是我们选择一个不包含 $0, 1$ 的区间 $-2$。
这两个都是非常好维护的，但是作者是一个长代码恐惧症，于是为了方便书写代码挖掘了几个性质：
> 我们将 $pre'_i = 0$ 的位置挖掉过后形成的每个区间 $[l, r]$ 必然满足 $s_{l}$ 为 `(` 而 $s_{r + 1}$ 为 `)`，即一定可以选择这个区间进行 $-2$。
这是为什么？因为最小值 $pre'_i = 0$ 一定满足 $pre'_{i - 1} = 1 / -1$，而 $0$ 为最小，所以 $pre'_{i - 1} = 1$，即 $s_i$ 为 `)`，那么前方区间 $[l, i - 1]$ 的 $s_{i - 1 + 1} = s_i$ 一定是 `)`，同理易证左括号和下面结论：
> 我们将 $pre'_i = 0,1$ 的位置挖掉过后形成的每个区间 $[l, r]$ 必然满足 $s_{l}$ 为 `(` 而 $s_{r + 1}$ 为 `)`，即一定可以选择这个区间进行 $-2$。
代码就是两个双指针的事情。
为了体现代码多短特意删去了无用部分。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, inf = 1e9;
int n, k, pre[N];
char str[N], s[N];
vector <int> vec[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> str[i], pre[i] = pre[i - 1] + (str[i] == '(' ? 1 : -1);
if (pre[n] != 0) return cout << "0\n1 1\n", 0;
int mn = inf, qwq = inf;
for (int i = 1; i <= n; i ++ ) qwq = min(qwq, pre[i]);
for (int i = 1; i <= n; i ++ ) if (pre[i] == qwq) mn = i + 1;
for (int i = mn; i <= n; i ++ ) s[i - mn + 1] = str[i];
for (int i = 1; i < mn; i ++ ) s[n - mn + 1 + i] = str[i];
for (int i = 1; i <= n; i ++ ) pre[i] = pre[i - 1] + (s[i] == '(' ? 1 : -1);
for (int i = 1; i <= n; i ++ ) vec[pre[i]].push_back(i);
auto get = [&](int a) -> int{ return (a <= n - mn + 1 ? a + mn - 1 : a - (n - mn + 1)); };
int ans = vec[0].size(), now = 0;
int pl = 1, pr = 1, nowl = 1;
for (int i = 1; i <= n; i ++ ){
if (pre[i] == 0 || pre[i] == 1){
int qwq = vec[0].size() + now;
if (qwq > ans && nowl <= i) ans = qwq, pl = get(nowl), pr = get(i);
nowl = i + 1, now = 0;
}
else if (pre[i] == 2) now ++ ;
}
now = 0, nowl = 1;
for (int i = 1; i <= n; i ++ ){
if (pre[i] == 0){
int qwq = now;
if (qwq > ans && nowl <= i) ans = qwq, pl = get(nowl), pr = get(i);
nowl = i + 1, now = 0;
}
else if (pre[i] == 1) now ++ ;
}
cout << ans << "\n" << pl << " " << pr << "\n";
}
```