题目链接：https://codeforces.com/contest/1905/problem/F
题意简述
对一个排列 \(p\)，一个下标 \(x\) 被称作“好下标”当且仅当 \(\forall y < x\) 满足 \(p_y < p_x\)，且 \(\forall y> x\) 满足 \(p_y > p_x\)。记 \(f(p)\) 为 \(p\) 中好下标的个数。
给定排列 \(p\)，你必须选择 \(l \le r\)，交换 \(p_l\) 与 \(p_r\)。求交换后 \(f(p)\) 的最大值。
题解
显然 \(x\) 是好下标等价于 \(p_x = x\) 且 \(\max\limits_{1 \le i \le x} p_i= x\) 且 \(\min\limits_{x \le i \le n} p_i= x\)，也就是可以线性判断原序列中所有下标是否已经是好下标。
首先关注如下的问题：一次交换会对一个位置是否是好下标产生什么样的影响？不加证明地，给出下列结论：
-
若 \(x\) 已经是好下标，所有交换 \(l \le x \le r\) 都会使其变得不再是好下标。也就是，修改 \((l, r)\) 会导致的答案减小可以简单地使用前缀和计算。
-
若 \(p_x = x\)，且左右各只有一个元素不满足好下标的条件，则只有交换这两个元素能使 \(x\) 变为好下标。
-
若 \(p_x > x\)，且左侧元素均小于 \(x\)，右侧只有一个元素不大于 \(x\)，则这个元素一定等于 \(x\)，且只有交换元素 \(p_x\) 和 \(x\) 能使 \(x\) 变为好下标。
-
对称地，若 \(p_x < x\)，且右侧均大于 \(x\)，左侧只有一个元素不小于 \(x\)，则这个元素一定等于 \(x\)，且只有交换元素 \(p_x\) 和 \(x\) 能使 \(x\) 变为好下标。
-
否则，\(x\) 永远无法成为好下标。
我们可以看到，可以使答案增加的交换的个数是 \(O(n)\) 的，因此我们先找到这些交换，用它们造成的结果更新答案即可。除此之外，还有可能不存在使答案增加的交换。这时我们的交换一定尽量影响尽可能少的元素，即枚举 \((i , i+1)\) 即可。
代码实现
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), pos(n + 1), pre_max(n + 1), suf_min(n + 1);
fenwick_tree<int> pre_tr(n + 2), suf_tr(n + 2);
for (int i = 1; i <= n; i++) {
cin >> a[i], suf_tr.add(a[i], 1), pos[a[i]] = i;
}
for (int i = 1; i <= n; i++) { pre_max[i] = max(pre_max[i - 1], a[i]); }
suf_min[n] = a[n];
for (int i = n - 1; i >= 1; i--) { suf_min[i] = min(suf_min[i + 1], a[i]); }
map<pair<int, int>, int> add_modifies;
int now = 0, ans = 0;
vector<int> feas(n + 1), pre_feas(n + 1, 0);
for (int i = 1; i <= n; i++) {
suf_tr.add(a[i], -1);
if (a[i] == i && pre_tr.sum(1, i) == i - 1 &&
suf_tr.sum(i + 1, n + 1) == n - i) {
now++;
feas[i] = true;
} else if (a[i] == i && pre_tr.sum(1, i) == i - 1 - 1 &&
suf_tr.sum(i + 1, n + 1) == n - i - 1) {
add_modifies[{pos[pre_max[i]], pos[suf_min[i]]}]++;
}
if (a[i] > i && pre_tr.sum(1, i) == i - 1 &&
suf_tr.sum(i + 1, n + 1) == n - i - 1) {
add_modifies[{i, pos[i]}]++;
}
if (a[i] < i && pre_tr.sum(1, i) == i - 1 - 1 &&
suf_tr.sum(i + 1, n + 1) == n - i) {
add_modifies[{pos[i], i}]++;
}
pre_tr.add(a[i], 1);
}
for (int i = 1; i <= n; i++) { pre_feas[i] += pre_feas[i - 1] + feas[i]; }
for (int i = 1; i < n; i++) { ans = max(ans, now - feas[i] - feas[i + 1]); }
for (auto [p, c] : add_modifies) {
auto [l, r] = p;
ans = max(ans, now + c - (pre_feas[r] - pre_feas[l - 1]));
}
cout << ans << "\n";
}