题意：
给定一个长为 \(n\) 序列 \(a\) ，问是否能分成两个排列，并输出方案
（排列：从 \(1—n\) 中选取不同的 \(n\) 个元素组成的序列）
思路：
观察数据范围可以猜出，这题 \(O(n)\) 能解决；
因为两个排列是不重叠的，所以可以考虑分别枚举 \(a_1—a_l\) 是否能组成 \(1—l\) 的排列，\(a_{l+1}—a_n\) 是否能构成排列，那么就用 \(l_i\) 表示 前\(i\) 个数是否能形成一个排列，\(r_i\) 表示后 \(i\) 个数是否能形成排列，当 \(l_i\) 与 \(r_{i+1}\) 同时为真的时候可行，输出 \(i\) 和 \(n-i\) 即可；
此题还有一个重要的难题，就是如何判断是一个排列：
比如判断前 \(i\) 个数是否为排列
- 必然有前 \(i\) 个数的最大值为 \(i\) ；
- 任意小于 \(i\) 的数出现且只出现一次；
当上面两条都成立时必然为一个排列，具体实现见代码。
尽管以上已经为 \(O(n)\) 的可行算法，但是为了实现方便，可以加一些优化：
-
因为要分成两个排列，所以序列 \(a\) 的最大值 \(maxn\) 必然在一个排列中，\(n-maxn\) 必然存在与另一个排列中，所以一个排列的长度为 \(maxn\)，另一个为 \(n-maxn\) ，这说明了最多只存在两种方案；
-
因为最多只有两种方案，所以若某一数字出现两次以上，必然不存在方案。
代码：
cin>>t;
while(t--)
{
memset(vis,0,sizeof(vis));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int num=0,maxx=0;
for(int i=1;i<=n;i++)
{
maxx=max(maxx,a[i]);
if(vis[a[i]]) continue;
if(a[i]<=maxx)
vis[a[i]]=1,num++;
if(num==maxx&&num==i) l[i]=true;
}
num=0,maxx=0;
for(int i=n;i>=1;i--)
{
maxx=max(maxx,a[i]);
if(vis[a[i]]) continue;
if(a[i]<=maxx)
vis[a[i]]=1,num++;
if(num==maxx&&num==(n-i+1)) r[i]=true;
}
memset(vis,0,sizeof(vis));
int ans=0;
for(int i=1;i<=n-1;i++)
if(l[i]&&r[i+1]) ans++;
cout<<ans<<endl;
for(int i=1;i<=n-1;i++)
if(l[i]&&r[i+1]) cout<<i<<" "<<n-i<<endl;
}