我将会给你一道题，讲解这道题的最简单解法，讲解的时候应当保证你使用的不同符号使用尽可能少，以及最后给...

Question

我将会给你一道题，讲解这道题的最简单解法，讲解的时候应当保证你使用的不同符号使用尽可能少，以及最后给出本题尽可能简洁实现的完整代码（为了 OI 选手可读性，允许在不影响正确性的情况下牺牲一部分运行效率），另外还请总结所有的关键结论或关键步骤（这一点，忽略细枝末节的地方）。

另外我提供一份我实现的 $O(n^2)$ 做法（已经证明答案正确性是可以保证的）

cpp
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
const int maxn=2e5+5;
int n,p[maxn];
bool fail=0;
int sol(int L,int R,bool allow_all){
	if(R-L+1==1)return 0;
	int res=0;
	int l=L;
	while(l<=R){
		int i=l,r=p[l];
		while(i<r){
			i++;
			ckmx(r,p[i]);
		}
		if(l==L&&r==R&&!allow_all){
			fail=1;
			return -1;
		}
		if(l==r){
			l=r+1;
			continue;
		}
		reverse(p+l,p+r+1);
		res+=sol(l,r,(l!=L||r!=R))+1;
		l=r+1;
		if(fail)return -1;
	}
	return res;
}
void solve(int id_of_test){
	read(n);
	FOR(i,1,n){
		read(p[i]);
	}
	int res=sol(1,n,1);
	if(fail){
		puts("-1");
	}else{
		printf("%d\n",res);
	}
	fail=0;
}
int main()
{
	int T;
	read(T);
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}
/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法对应上？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*/

Answer 1

可以做到 $O(n)$ 时间、 $O(n)$ 空间，而且实现只需要一个栈。

你的做法是“从大区间向下分块，并实际翻转”。我们把它改成：

从单个数开始向上合并；不实际翻转，而是同时维护“变成升序”和“变成降序”的代价。

下面沿着你的递归思路解释。

一、把“递归分块”变成“合并相邻块”

我们维护一些块。每个块都满足：

位置连续，并且包含的数恰好组成一个连续的值域。 块内不要求有序。

对于相邻的两个块，记左块为 a，右块为 b，各自的值域端点为 mn, mx。我们允许两种合并：

拼接方向	合并条件	含义
升序拼接	`a.mx + 1 == b.mn`	左块的数全部小于右块，并且值域相接
降序拼接	`b.mx + 1 == a.mn`	左块的数全部大于右块，并且值域相接

合并后，仍然是一个位置连续、值域连续的块。

注意：mn, mx 是值域端点，不是下标。

为什么只考虑这两种拼接？

题目的限制决定了：操作只能形成“先处理大区间，再处理内部小区间”的递归结构。

以把当前块变成升序为例：

如果不翻转整个块，那么分别处理的小块，其值域本来就按升序排列。
如果先翻转整个块，那么这些小块在翻转之前，其值域按降序排列。

整体翻转还会把每个小块内部反过来，这一点稍后用两个代价处理。

因此，你的递归倒过来看，就是不断进行升序拼接或降序拼接。一次拼接多个块，也可以拆成若干次拼接两个块。

二、每个块维护两个代价

每个块除了 mn, mx，再维护：

up：把这个块变成升序的最少操作数。

down：把这个块变成降序的最少操作数。

两种目标都遵守题目中的操作限制。对于单个数，显然：

text
up = down = 0

1. 升序拼接

此时左块的数全部小于右块。

要变成升序，分别把两个块变成升序即可：

up=up_{\text{左}}+up_{\text{右}}.

要变成降序，则先整体翻转一次。

这里最容易想错：整体翻转不仅交换了两个块，还把每个块内部也反过来了。

把“反转后的子块”整理成降序，等价于把“原来的子块”整理成升序，操作次数不变。因此：

down=up+1.

也就是：

text
新的 up   = 左块 up + 右块 up
新的 down = 新的 up + 1

2. 降序拼接

完全对称：

text
新的 down = 左块 down + 右块 down
新的 up   = 新的 down + 1

这些方案一定合法：两个子块互不相交；需要整体翻转时，把它放在最前面，后面的操作都被它包含。把子块中的操作位置镜像，也不会改变包含或不相交的关系。

用样例理解

对于：

text
3 4 1 2

先分别合并 3 4 和 1 2。它们都是升序块，所以都有：

text
up = 0, down = 1

这两个块按值域降序拼接，因此：

text
新的 down = 1 + 1 = 2
新的 up   = 2 + 1 = 3

得到答案 $3$ 。

三、为什么可以“能合并就立刻合并”？

这是栈算法最关键的正确性。

假设当前有多个可选的合并。

如果两次合并涉及的块互不相交，显然互不影响。

如果它们有影响，那么一定是在三个相邻块中，可以合并左边两个，也可以合并右边两个。

这时，两次合并的方向一定相同。

例如，假设左、中两块可以升序合并，而中、右两块可以降序合并，那么：

text
左块最大值 = 中块最小值 - 1
右块最大值 = 中块最小值 - 1

左右两块出现了相同的数，与排列中的数互不相同矛盾。另一种方向相反的情况同理。

所以，存在冲突的合并选择，只可能是：

text
三个块按值域连续升序排列

或者：

text
三个块按值域连续降序排列

此时，无论先合并哪边，最后都一样。

例如连续升序拼接时，最终 up 都是三个块的 up 之和，down 都是在此基础上加一。降序拼接同理。

因此：

合并选择互不影响，或者仅仅相当于改变同方向拼接的括号；既不影响能否合成整体，也不影响最终代价。

你的正确递归方案反过来，对应某一种完整合并过程，而上述转移恰好统计它的翻转次数。既然合并顺序不影响结果，栈采用任意可行的合并顺序，得到的也是同一个最优答案。

四、用栈完成合并

从左到右读入排列：

把当前数作为一个单点块入栈。
只要栈顶两个块能合并，就合并它们，并继续检查新的栈顶两个块。
最后只剩一个块，输出它的 up；否则输出 -1。

为什么只检查栈顶？因为此前栈内已经没有可以合并的相邻块；加入或合并一个新块后，只有它与前一个块之间的关系可能发生变化。

每个数入栈一次，每次合并让块数减少一，所以总共至多合并 $n-1$ 次。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。 不需要实际翻转，也没有递归深度问题。

五、完整代码

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

struct Node {
    int mn, mx;
    int up, down;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<Node> st;
        st.reserve(n);

        for (int i = 0, x; i < n; ++i) {
            cin >> x;
            st.push_back({x, x, 0, 0});

            while (st.size() >= 2) {
                Node a = st[st.size() - 2];
                Node b = st.back();

                if (a.mx + 1 == b.mn) {
                    // 升序拼接
                    a.mx = b.mx;
                    a.up += b.up;
                    a.down = a.up + 1;
                } else if (b.mx + 1 == a.mn) {
                    // 降序拼接
                    a.mn = b.mn;
                    a.down += b.down;
                    a.up = a.down + 1;
                } else {
                    break;
                }

                st.pop_back();
                st.back() = a;
            }
        }

        cout << (st.size() == 1 ? st[0].up : -1) << '\n';
    }

    return 0;
}

关键结论总结

递归可以倒过来做。 从单点开始，合并位置相邻、值域相接的块，拼接方向只能是升序或降序。
不需要实际翻转。 维护 up, down：升序拼接时 up 相加、down = up + 1；降序拼接时反过来。
能合并就合并。 有冲突的合并选择一定同方向，只相当于改变括号，不影响结果。
用栈在线处理。 最后剩一个块输出 up，否则无解；时间和空间均为 $O(n)$ 。