题目理解

我们有一个长度为 $n$ 的数组，需要用 Alice 的选择排序函数作为子程序来排序整个数组。可用操作：

1. 前缀排序：排序前 $i$ 个元素，成本 $i^2$
2. 后缀排序：排序后 $i$ 个元素，成本 $i^2$

每种操作最多使用一次，顺序任意。求最小总成本。

关键观察

1. 操作的效果

Alice 的排序是选择排序，会将指定区间完全排序成非递减顺序。

2. 只需要考虑两种情况

由于每种操作最多一次，只有三种可能：

• 只做前缀排序
• 只做后缀排序
• 先前缀后后缀，或先后缀后前缀

实际上，由于数组排序的对称性，我们可以只分析两种顺序：

• 先做长度 $i$ 的前缀排序，再做长度 $j$ 的后缀排序
• 先做长度 $j$ 的后缀排序，再做长度 $i$ 的前缀排序

3. 后一次操作可能破坏前一次的结果吗？

这是一个重要问题。

假设我们先做前缀排序（长度 $i$），数组变为：

[已排序部分] [未排序部分]

再做后缀排序（长度 $j$）：

• 如果 $j$ 很大，会覆盖整个数组，那么第一次的操作结果可能会被覆盖
• 但后缀排序只改变后 $j$ 个元素，不会干扰前 $n-j$ 个元素

所以两次操作的区间可能有重叠，但重叠部分会被第二次操作重新排序。

4. 什么时候数组完全有序？

关键思想：如果先做长度 $i$ 的前缀排序，再做长度 $j$ 的后缀排序，数组排序成功的条件是：

• 前 $n-j$ 个元素（前缀排序的结果不受后缀影响的部分）必须已经是排序好的
• 后缀排序后，整个数组有序

更精确地说：

• 令 $L = n - j$（前 $L$ 个元素不受后缀排序影响）
• 前 $i$ 个元素经过前缀排序后有序
• 如果 $L \le i$，前缀排序的结果会部分被覆盖；如果 $L > i$，前缀排序只能影响前 $i$ 个，那么 $i+1$ 到 $L$ 这些元素必须自己已经有序

实际上，更简单的思路是直接枚举两种情况。

解题方案

情况一：先前缀排序，后缀排序

设先做长度 $p$ 的前缀排序，再做长度 $q$ 的后缀排序，总成本 $p^2 + q^2$。

分析条件：

1. 做完前缀排序后，前 $p$ 个元素有序
2. 后缀排序会影响后 $q$ 个元素，即数组的 $[n-q+1, n]$ 部分（1-indexed）
3. 做完后缀排序后，整个数组有序

令 $L = n - q$（前 $L$ 个元素不会被后缀排序影响）

• 前 $L$ 个元素必须已经有序（来自前缀排序的结果或原始数组）
• 后缀排序必须在 $L$ 之后的位置正确放置剩余元素

实际上，我们可以这样想：

• 对于数组 $a[1..n]$（1-indexed），
• 后缀排序后，后 $q$ 个元素变成 $n-q+1$ 到 $n$ 位置的有序序列
• 最终数组要完全有序，意味着：
  • 前 $n-q$ 个元素必须 $\le$ 后 $q$ 个元素的最小值
  • 前 $n-q$ 个元素必须本身有序
  • 后 $q$ 个元素就是排序后的结果

所以关键条件是：

• 原数组的后 $q$ 个元素，排序后必须恰好是数组的 $q$ 个最大值
• 前 $n-q$ 个元素无法通过后缀排序改变，它们必须已经有序且小于等于后 $q$ 个元素的最小值

但前 $n-q$ 个元素中的一部分可能被前缀排序影响。

更实用的方法是：

1. 枚举后缀排序长度 $q$
2. 确定需要 $p$ 至少多大，通过前缀排序使前 $n-q$ 个元素有序

情况二：先后缀排序，再前缀排序

对称分析即可。

算法实现

预处理

1. 计算原数组的后缀是否有序
2. 计算原数组的前缀是否有序
3. 计算前缀排序后，能使哪些前缀有序

具体步骤

定义数组 $a[1..n]$

令 $pre[i]$ 表示 $a[1..i]$ 是否有序 令 $suf[i]$ 表示 $a[i..n]$ 是否有序

对于先做长度 $p$ 的前缀排序，再做长度 $q$ 的后缀排序：

要求：

• 对 $k = n-q+1$ 到 $n$ 进行后缀排序后，这些位置成为全局最大值
• 前 $n-q$ 个位置必须已经 $\le$ 后 $q$ 个位置的最小值

实际上，等价于：

• 原数组的第 $n-q+1$ 到 $n$ 个元素排序后，就是全局最大的 $q$ 个元素
• 这要求原数组的第 $1$ 到 $n-q$ 个元素都 $\le$ 第 $n-q+1$ 到 $n$ 个元素的最小值
• 并且前 $n-q$ 个元素通过前缀排序后必须有序

第 3 个条件：如果 $p \ge n-q$，则前缀排序覆盖了整个前 $n-q$ 部分，自动满足；如果 $p < n-q$，则前 $p$ 个有序，但 $p+1$ 到 $n-q$ 位置需要原数组已经有序且满足值条件。

但在实现中，通常枚举 $q$ 然后计算最小的 $p$ 更简单。

更简洁的方法 - 找分界点

观察最终排序后的数组 $sorted$：

• 如果只用一次操作，数组本身就是有序或逆序的特殊情况
• 如果用两次操作，存在一个分割点 $k$，使得：
  • 前 $n-q$ 个元素最终等于 $sorted[1..n-q]$
  • 后 $q$ 个元素最终等于 $sorted[n-q+1..n]$
  • 并且这些位置上的原始元素可以通过一次前缀/后缀排序完成

实际上，这等价于找最大 $L$ 使得 $a[1..L]$ 可以通过一次前缀排序变成 $sorted[1..L]$，类似找最大 $R$ 使得 $a[R..n]$ 可以通过一次后缀排序变成 $sorted[R..n]$。

然后答案就是 $\min(L^2 + (n-L)^2)$ 之类的。

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 情况1：只做前缀排序
    // 检查原数组是否本身就是有序的
    bool sorted = true;
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i-1]) {
            sorted = false;
            break;
        }
    }
    if (sorted) {
        cout << "0\n";
        return 0;
    }
    
    // 情况2：只做一次前缀排序
    // 实际上就是对整个数组做一次排序
    ll ans = 1LL * n * n;  // 只用一次前缀排序整个数组
    
    // 情况3：只做一次后缀排序
    ans = min(ans, 1LL * n * n);
    
    // 情况4：先前缀后后缀
    // 枚举后缀长度 q
    for (int q = 1; q <= n; q++) {
        // 检查是否能通过后缀排序后 q 个元素完成
        // 需要前 n-q 个元素已经 <= 后 q 个元素的任意值且相对有序
        // 更简单的：找最小的 p 使得前缀排序 p 后，再后缀排序 q 可行
        
        // 实际实现中，可以预处理需要前缀排序的最小长度
        // 这里采用混合判断
        
        // 设 L = n - q
        // 后缀排序只影响位置 L+1..n
        // 所以位置 1..L 必须已经有序且都 <= min(a[L+1..n])
    }
    
    // 情况5：先后缀后前缀
    // 对称分析
    
    // 更规范的实现方式：
    // 1. 计算 right[i] = 从 i 开始到 n 是否需要排序才能成为全局后缀部分
    // 2. 计算 left[i] = 从 1 到 i 是否需要排序才能成为全局前缀部分
    
    // 求非递减序列排序后的数组
    vector<int> b = a;
    sort(b.begin(), b.end());
    
    // 从左到右找第一个需要修改的位置
    int left_fix = -1;
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) {
            left_fix = i;
            break;
        }
    }
    
    // 从右到左找第一个需要修改的位置
    int right_fix = -1;
    for (int i = n-1; i >= 0; i--) {
        if (a[i] != b[i]) {
            right_fix = i;
            break;
        }
    }
    
    // 如果数组已经有序
    if (left_fix == -1) {
        cout << "0\n";
        return 0;
    }
    
    // 找最小的 x 使得对前缀 x 排序后，剩余部分满足条件
    // 实际上，答案就是 min( (right_fix+1)^2, (n-left_fix)^2, (right_fix+1)^2 + (n-left_fix)^2? 不对)
    
    // 观察样例：
    // [3,2,5,5,4,1] sorted = [1,2,3,4,5,5]
    // left_fix = 0 (a[0]=3 != 1)
    // right_fix = 5 (a[5]=1 != 5)
    // 前缀排序需要长度至少是 right_fix+1 = 6? 不对，实际最优是前缀3后缀4
    
    // 所以需要更精细的枚举
    
    // 方法：枚举第一个操作的长度，检查第二个操作是否可行
    
    ans = 1LL * n * n;  // 初始化为只用一次操作的最大值
    
    // 尝试先做前缀排序
    for (int p = left_fix+1; p <= n; p++) {
        // 对前 p 个元素排序
        // 检查通过后缀排序能否完成整个排序
        // 后缀排序的长度至少需要 n - (第一个违反有序的位置)
        vector<int> c = a;
        sort(c.begin(), c.begin() + p);
        
        // 检查从右到左
        int need = 0;
        for (int i = n-1; i >= 0; i--) {
            if (c[i] != b[i]) {
                need = max(need, n - i);
            }
        }
        if (need > 0) {
            ans = min(ans, 1LL * p * p + 1LL * need * need);
        }
    }
    
    // 对称地，尝试先做后缀排序
    for (int q = n-right_fix; q <= n; q++) {
        vector<int> c = a;
        sort(c.begin() + (n - q), c.end());
        
        int need = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] != b[i]) {
                need = max(need, i + 1);
            }
        }
        if (need > 0) {
            ans = min(ans, 1LL * q * q + 1LL * need * need);
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

注意：上面代码的复杂度是 $O(n^2)$，对于 $n \le 10^6$ 不可行。实际解题需要 $O(n)$ 的预处理和判断。由于完整的高效解法需要较长的推导，这里提供的是可读但效率较低的版本，帮助理解思路。竞赛中需要进一步优化为线性或 $O(n \log n)$。