题面：
(Description)
众所周知，排序方法有许多种。例如：简单易懂的冒泡排序，平均复杂度较优的快速排序，以及不基于比较的基数排序等等。
现在，小(D)得到了一个自然数序列({a_1,a_2,⋯,a_n})。他想要对其按照从小到大的顺序进行排序（即使得每个元素均严格不大于他的后继元素）。但由于基于比较的排序算法复杂度下界已经被证明为(Θ(nlog2n))，所以小(D)决定尝试一种全新的排序算法：翻转排序。
在翻转排序中，小 (D) 在每次操作中，可以选择一个区间 ([l,r] (1≤l≤r≤n))，并翻转 (a_l,a_{l+1},⋯,a_r)。即，在该次操作完后，序列将会变为 (a_1,a_2,⋯,a_{l−1},a_r,a{r−1},⋯,a_{l+1},a_l,a_{r+1},a_{r+2},⋯,a_n)。
例如，对于序列 ([1,6,2,4,3,5])，若选择区间 ([2,4]) 进行翻转，则将会得到 ([1,4,2,6,3,5])。
定义一次操作的代价为 (r−l+1)，即翻转的区间长度。定义一个操作序列的代价为每次操作的代价之和。现在，请你帮助小 (D) 求出一个代价足够小的操作序列（你并不一定要求出代价最小的操作序列）。
(Input)
第一行一个正整数(n)，表示序列长度。
第二行(n)个空格隔开的非负整数，表示小(D)得到的自然数序列({{a_i}})。
(Output)
输出若干行，每行两个空格隔开的正整数 (l,r) ((1≤l≤r≤n))，表示一次翻转区间([l,r])的操作。
最后输出一行(-1 -1)，标志着操作序列的结束。
(Sample Input)
4 1 3 2 4
(Sample Output)
2 3 -1 -1
(Hint)
1.下发文件中提供了 (checker.cpp)，该程序将对于其所在目录下的 (sort.in)，判断其所在目录下的 (sort.out) 是否为一个正确的操作序列。若正确，将给出该操作序列的代价。若不正确，将给出错误信息。选手可以借助该程序来更好地检查自己的程序是否正确。
运行时，必须保证 (sort.in) 为一个合法的输入，且需保证 (sort.out) 符合题目中描述的输出格式，否则出现任何结果均有可能。
(checker.cpp:)
#include <algorithm>
#include <cstdio>
int arr[50005];
int main()
{
FILE *fin = fopen("sort.in", "r"), *fout = fopen("sort.out", "r");
if (!fin)
{
puts("INVALID : File sort.in not found.");
return -1;
}
if (!fout)
{
puts("INVALID : File sort.out not found.");
return -1;
}
int n;
fscanf(fin, "%d", &n);
for (int i = 0; i < n; i++)
fscanf(fin, "%d", arr + i);
int l, r, sum = 0;
while (~fscanf(fout, "%d%d", &l, &r))
{
if (l == -1 && r == -1)
break;
sum += r - l + 1;
if (l <= 0 || l > n)
{
printf("INVALID : l = %d is not in range [1, %d].
", l, n);
return -1;
}
if (r <= 0 || r > n)
{
printf("INVALID : r = %d is not in range [1, %d].
", r, n);
return -1;
}
if (l > r)
{
printf("INVALID : %d = l > r = %d.
", l, r);
return -1;
}
if (sum > 20000000)
{
puts("INVALID : Too much cost.");
return -1;
}
std::reverse(arr + --l, arr + r);
}
bool f = true;
for (int i = 1; i < n; i++)
f &= arr[i] >= arr[i - 1];
if (!f)
{
puts("INVALID : Not sorted.");
return -1;
}
printf("VALID : Total cost is %d.
", sum);
return 0;
}
2.对于所有测试数据，保证 (1≤n≤50000)，且 (0≤ai≤10^9)。
(Solution)
这道题结合了快速排序和归并排序的思想。
先考虑(01)串：
对于(01)串，我们考虑类似归并排序的形式，分治下去，回溯时左半部分的右边均为(1)，右半部分的左边均为(0)，进行一次(Reverse)即可
再考虑正解：
我们可以类似快速排序，选择一个基准数(stdq)，将满足(a_i leq stdq)的(a_i)视为(0)，(1)同理，再按(01)串的方法处理即可
在代码实现的过程中，我们用离散化来实现，其中(pre[])用于维护大小关系，具体见代码
(Code:)
#include<bits/stdc++.h>
using namespace std;
namespace my_std
{
typedef long long ll;
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define pf printf
inline ll read()
{
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch))
{
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch))
{
sum=(sum<<1)+(sum<<3)+(ch^48);
ch=getchar();
}
return sum*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
}
using namespace my_std;
const int N=5e4+50;
int n,pre[N],stdq;
struct qq
{
int v,val;
}a[N];
bool cmp(qq a,qq b)
{
return a.v<b.v;
}
inline void work(int l,int r)
{
if(l==r) return ;
int mid=(l+r)>>1;
work(l,mid),work(mid+1,r);
int lefty=mid,righty=mid,lp=mid,rp=mid+1;
while(lp>=l&&pre[lp]>stdq) lefty=lp--;
while(rp<=r&&pre[rp]<=stdq) righty=rp++;
if(lefty!=righty)
{
pf("%d %d
",lefty,righty);
reverse(pre+lefty,pre+righty+1);
}
}
inline void mergesort(int l,int r)
{
if(l==r) return;
int mid=stdq=(l+r)>>1;
work(l,r);
mergesort(l,mid),mergesort(mid+1,r);
}
int main(void)
{
n=read();
fr(i,1,n) a[i].v=read(),a[i].val=i;
sort(a+1,a+n+1,cmp);
fr(i,1,n) pre[a[i].val]=i;
mergesort(1,n);
puts("-1 -1");
return 0;
}