题解：CF1973E Cat, Fox and Swaps

· · 题解

思路参考官方题解，但其中对官方题解的思路和略过的部分进行了详细补充，证明了所有题解草草略过的部分，希望读者能认真阅读超链接部分的文字。

开始前，先判断排列是否已经有序，若有序，答案为 \sum\limits_{l=1}^{n}\sum\limits_{r = l}^{n} 1 = \dfrac{2n (2n + 1)}{2} = 2n^2+n，不进行过多讨论。

首先考虑 l = r 的对子，若 i \neq p_i，此时 l = r = i + p_i，找出所有这样的 i，数量记作 c，讨论：

观察到若要交换 x, y，可以借助第三个数 z 使得不直接交换 x, y，而是交换 x,z 和 y, z 达到同样的效果（z 位置不变，x, y 交换），证明。其实如果 x = z 或者 y = z，相当于直接交换了 x, y，下文不区分这个了。

设 L 是最小的使得 L \neq p_L 的 L，R 是最大的使得 R \neq p_R 的 R。

注意到 L \neq n, R \neq 1，否则排序有序。那么我们可以得到使 L, R 至少与一个其他数交换来使排列有序的必要条件：l \in [1, L + n], r \in [R + 1, 2n]。

事实上这是充分的。

先把不等式摆上来：l \le L + n，r \ge R + 1。

注意现在统计的数对是 l < r 的，虽然 L + n \ge R + 1 有可能成立。下面的讨论默认 l < r。

引理：对于任意的 X \in [L, R - 1]，一定存在一个 x \in [l, r]，使得 1 \le x - X \le n，证明。

这样，X \in [L, R - 1] 的数可以借助数 x - X 两两相互交换了。进一步地，X\in[L, R - 1] 的数可以和 X + 1 交换，具体步骤：

这样，[L, R] 中的所有数可以相互随意合法交换且不影响其他数，可以完成排序，充分性证毕。

最后统计答案，答案是 l \in [1, L + n], r \in [R + 1, n] 中，l < r 的 (l, r) 数量（L + n \ge R + 1 可能成立），我居然没想到 O(1) 的数学做法，有无大佬教教。

从 R + 1 到 2n 枚举右端点 r，那么合法的 l \in [1, \min(L + n, r - 1)]。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<int> p(n);
        set<int> st;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            cin >> p[i];
            if (i + 1 != p[i])
                st.insert(p[i] + i + 1);
        }
        if (is_sorted(p.begin(), p.end())) {
            cout << 2ll * n * (2 * n + 1) / 2 << "\n";
            continue;
        }

        ll ans = st.size() == 1;

        int L = n, R = 1;
        for (int i = 0; i < n; i++) {
            if (p[i] != i + 1) {
                L = min(L, i + 1);
                R = max(R, i + 1);
            }
        }

        for (int i = R + 1; i <= 2 * n; i++)
            ans += min(L + n, i - 1);

        cout << ans << "\n";
    }
    return 0;
}

闲话