CF1905F Field Should Not Be Empty 题解

happybob · 2024-01-26 20:38:42 · 题解

特判如果排列初始时是 1,2,\cdots,n，输出 n-2。

如果不是，那么我们交换两个后的结果一定大于等于初始值。

考虑新增的贡献是什么？假设交换 p_i,p_j(i < j)，那么新增的贡献必然是一个 k \in [i,j]，交换前 k 不是好的，交换后是好的。

注意到位置 i 是好的的必要条件是 p_i=i。

考虑枚举上文的 k。接着考虑交换的 i,j 会怎么样。

第一种可能是，i=k 或 j=k。那么根据必要条件，我们知道换的一定是 i 和 p_i 这两个位置。

第二种，i \neq k 且 j \neq k，那么交换的必然是 [1,i) 中的最大值点和 (i,n] 中的最小值点，证明显然。

然后现在有 O(n) 对 (i,j)，每一对算贡献都可以讨论贡献然后前缀和做到 O(1)。预处理有个 O(n \log n) 的复杂度，但是可能可以优化？但是我们避开了树状数组或线段树等数据结构！

#pragma GCC optimize("-Ofast,fast-math,-inline")
#pragma GCC target("avx,sse,sse2,sse3,popcnt")
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <set>
#include <vector>
using namespace std;

const int N = 2e5 + 5;

int t, n, p[N];
int minn[N], maxn[N];
bool g[N], f[N];
int sf[N], sg[N];
int ra[N];

inline int query(int l, int r)
{
    if (l > r) swap(l, r);
    int nl = l + 1, nr = r - 1;
    nl = max(nl, p[r] + 1);
    nr = min(nr, p[l] - 1);
    int res = 0;
    if (nl <= nr)
    {
        res += sg[nr] - sg[nl - 1];
    }
    res -= (sf[r - 1] - sf[l]);
    res -= f[l];
    res -= f[r];
    res += (p[l] == r && (maxn[r - 1] == r) && (p[r] <= r - 1));
    res += (p[r] == l && maxn[l - 1] == l - 1);
    return res;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while (t--)
    {
        int sum = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> p[i], g[i] = f[i] = 0, ra[p[i]] = i;
        maxn[1] = p[1];
        for (int i = 2; i <= n; i++) maxn[i] = max(maxn[i - 1], p[i]);
        minn[n + 1] = (int)1e9;
        for (int i = n; i >= 1; i--) minn[i] = min(minn[i + 1], p[i]);
        if (is_sorted(p + 1, p + n + 1))
        {
            cout << n - 2 << "\n";
            continue;
        }
        set<int> s1;
        for (int i = 1; i <= n; i++)
        {
            f[i] = (p[i] == i) && (maxn[i - 1] == i - 1);
            g[i] = (p[i] == i) && (!s1.empty()) && (s1.upper_bound(p[i]) == --s1.end());
            s1.insert(p[i]);
            sum += f[i];
            sf[i] = sf[i - 1] + f[i];
            sg[i] = sg[i - 1] + g[i];
        }
        int ans = sum;
        for (int i = 1; i <= n; i++)
        {
            if (g[i])
            {
                ans = max(ans, sum + query(ra[maxn[i - 1]], ra[minn[i + 1]]));
            }
            if (p[i] != i) ans = max(ans, sum + query(i, p[i]));
        }
        cout << ans << "\n";
    }
    return 0;
}