题目大意就是给定的一个长为n的串只让对长度为偶数的区间的两半 半对半交换（而非翻转），用不超过9^6(最坏接受nlogn的算法)次操作完成排序。
方法，
第一开始并没有没有想到脑筋陷入了死点。
其实，就是采用往常的递推式思想，如果能解决了把1放在1处，那么剩下的就是个子问题。
怎样将1快速放到1处，其实1在1处不用在考虑。若1在中点位置（偶数情况下选靠右的中间位置）则通过其次交换即可。
剩下的就是两边，也只需依次交换就可将1放到中间。所以最坏需要两次。那么总时间复杂度最坏为2*n。
下面代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 10100;
int a[maxn],Id[maxn],n;
struct node{
int x, y;
node(int x=0,int y=0):x(x),y(y){}
};
vector<node> ans;
int Swap(int x1,int y1,int x2,int y2){
ans.push_back(node(x1,y2));
for(int i=x1,j=x2;i<=y1;i++,j++){
swap(Id[a[i]],Id[a[j]]);
swap(a[i],a[j]);
}
}
int main()
{
int T=0;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
Id[a[i]]=i;
}
ans.clear();
for(int i=1;i<=n;i++){
if(Id[i]==i) continue;
int m=(i+n+1)/2;
int id=Id[i];
if(id!=m){
if(id<m){
Swap(id,m-1,m,2*m-id-1);
}
else
Swap(2*m-id+1,m,m+1,id);
}
Swap(i,m-1,m,2*m-i-1);
}
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++){
printf("%d %d\n",ans[i].x,ans[i].y);
}
}
return 0;
}