所以线段树维护出的“值为 $1$ 的位置个数”恰好就是 $f(p)$。

性质 $2$

任何好下标都必须满足 $p_x=x$。因此若一次交换想新建好下标 $x$，它必须把值 $x$ 交换到位置 $x$，也就是第一类交换 (x, pos[x])。

性质 $3$

如果一次交换不移动位置 $i$，却想让 $i$ 变成好下标，那么它原本必须已经是固定点。此时所有破坏条件的元素只能分成左侧过大元素和右侧过小元素两类，而且两类个数相等。

一次交换至多处理每侧各一个，因此只有在两侧都恰好只有一个坏元素时可行，而且唯一可行交换就是把这两个坏元素交换，也就是第二类交换。

性质 $4$

除这两类交换外，任何交换都不会新建好下标，也不会修好某个已经是固定点但不合法的位置，因此不可能让答案更优。

结论

我们枚举了所有可能使答案变大的交换；对每个候选交换，线段树都能正确计算交换后的 $f(p)$。因此算法得到的最大值就是正确答案。

复杂度分析

单调栈与树状数组预处理是 $O(n \log n)$。

候选交换数量是 $O(n)$，每次在线段树上做常数次区间加减，复杂度也是 $O(\log n)$，所以枚举部分总复杂度仍为：

空间复杂度为：

参考代码

#include <bits/stdc++.h>
using namespace std;
struct aint
{
    vector<pair<int, int>> a;
    vector<int> lazy;
    void resize(int n)
    {
        a = vector<pair<int, int>>(4 * n);
        lazy = vector<int>(4 * n);
    }
    void init(int node, int left, int right)
    {
        a[node].second = (right - left + 1);
        if (left != right)
        {
            int mid = (left + right) / 2;
            init(2 * node, left, mid);
            init(2 * node + 1, mid + 1, right);
        }
    }
    void prop(int node, int left, int right)
    {
        a[node].first += lazy[node];
        if (left != right)
        {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    pair<int, int> merge(pair<int, int> a, pair<int, int> b)
    {
        if (a.first == b.first)
        {
            return pair<int, int>{a.first, a.second + b.second};
        }
        return min(a, b);
    }
    void update(int node, int left, int right, int st, int dr, int val)
    {
        prop(node, left, right);
        if (right < st || left > dr)
        {
            return;
        }
        if (st <= left && dr >= right)
        {
            lazy[node] += val;
            prop(node, left, right);
            return;
        }
        int mid = (left + right) / 2;
        update(2 * node, left, mid, st, dr, val);
        update(2 * node + 1, mid + 1, right, st, dr, val);
        a[node] = merge(a[2 * node], a[2 * node + 1]);
    }
};
struct bit
{
    vector<int> a;
    void resize(int n)
    {
        a = vector<int>(n + 1);
    }
    void update(int pos, int val)
    {
        int n = (int)a.size() - 1;
        for (int i = pos; i <= n; i += i & (-i))
        {
            a[i] += val;
        }
    }
    int query(int pos)
    {
        int ans = 0;
        for (int i = pos; i; i -= i & (-i))
        {
            ans += a[i];
        }
        return ans;
    }
    int query(int st, int dr)
    {
        return query(dr) - query(st - 1);
    }
};
int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--)
    {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        bool sortat = true;
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            if (a[i] != i)
            {
                sortat = false;
            }
        }
        if (sortat)
        {
            cout << n - 2 << '\n';
            continue;
        }
        vector<pair<int, int>> qui(n + 1);
        stack<int> s;
        bit tree;
        tree.resize(n);
        for (int i = 1; i <= n; ++i)
        {
            while (!s.empty() && a[s.top()] < a[i])
            {
                s.pop();
            }
            if (!s.empty())
            {
                qui[i].first = s.top();
            }
            if (tree.query(a[i], n) > 1)
            {
                qui[i].first = 0;
            }
            tree.update(a[i], 1);
            s.push(i);
        }
        while (!s.empty())
            s.pop();
        tree.resize(n);
        for (int i = n; i >= 1; --i)
        {
            while (!s.empty() && a[s.top()] > a[i])
            {
                s.pop();
            }
            if (!s.empty())
            {
                qui[i].second = s.top();
            }
            if (tree.query(1, a[i]) > 1)
            {
                qui[i].second = 0;
            }
            tree.update(a[i], 1);
            s.push(i);
        }
        aint lesgo;
        lesgo.resize(n);
        lesgo.init(1, 1, n);
        function<void(int, int)> upd = [&](int ind, int sign)
        {
            lesgo.update(1, 1, n, min(ind, a[ind]), max(ind, a[ind]), sign);
        };
        function<int()> count = [&]()
        {
            if (lesgo.a[1].first == 1)
            {
                return lesgo.a[1].second;
            }
            return 0;
        };
        function<void(int, int)> mySwap = [&](int i, int j)
        {
            upd(i, -1);
            upd(j, -1);
            swap(a[i], a[j]);
            upd(i, 1);
            upd(j, 1);
        };
        for (int i = 1; i <= n; ++i)
        {
            upd(i, 1);
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (qui[i].first && qui[i].second)
            {
                mySwap(qui[i].first, qui[i].second);
                ans = max(ans, count());
                mySwap(qui[i].first, qui[i].second);
            }
        }
        vector<int> pos(n + 1);
        for (int i = 1; i <= n; ++i)
        {
            pos[a[i]] = i;
        }
        for (int i = 1; i <= n; ++i)
        {
            int qui1 = i;
            int qui2 = pos[i];
            mySwap(qui1, qui2);
            ans = max(ans, count());
            mySwap(qui1, qui2);
        }
        cout << ans << '\n';
    }
}