[noi.ac_D1T2]sort

脑洞

题面

定义"翻转排序"：每次操作均为把区间$[l,r]$中所有数倒过来，即$swap(a[l],a[r])+swap(a[l+1],a[r-1])+...$。
每次操作的代价为$r-l+1$。
给一个序列$a$，用"翻转排序"给它排序，并把代价控制在$2*10^7$以内。

• $60pts$ $n\leq5000$
• $ex25pts$ $a[i]\in\{0,1\}$
• $100pts$ $n\leq5*10^4$

解析

感觉很符合$noip\_T2$难度。。。

$60pts$算法

仔细想想，"翻转"这个条件挺恶心的。
可以不"翻转"吗？那就只能交换相邻两个。

把序列扫$n$遍，每次只交换序列中相邻两个数。
这样每交换一次对应着消除一个逆序对，复杂度可控。
次数最多为$(n-1)*[(n-1)-1]/2\leq1.25*10^7$
但是我并不知道这种排序名字叫什么。。。

复杂度$O(n^2)$
代码在下一档。

$85pts$算法

这个有点搞笑。
直接归并排序就可以了。
每次归并后把左边的$1$区间和右边的$0$区间并在一起，翻转即可。
复杂度$O(nlogn)$
贴上代码。

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define pc(a) putchar(a)
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
int n,a[N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re int x)
{
  if(x>9) wri(x/10);
  pc(x%10+48);
}
il void solve(re int l,re int r)
{
  if(l==r) return;
  if(l==r-1)
  {
    if(a[l]>a[r]) swap(a[l],a[r]),printf("%d %d\n",l,r);
    return;
  }
  re int mid=l+r>>1,p1=0,p2=0;
  solve(l,mid);solve(mid+1,r);
  fp(i,l,mid) if(a[i]==1) {p1=i;break;}
  fp(i,mid+1,r) if(a[i]==1) {p2=i;break;}
  if(!p1) return;
  if(!p2) {printf("%d %d\n",p1,r);reverse(a+p1,a+r+1);return;}
  printf("%d %d\n",p1,p2-1);reverse(a+p1,a+p2);
  return;
}
int main()
{
  n=gi();
  fp(i,1,n) a[i]=gi();
  if(n<=5000)
  {
    fp(i,1,n)
      {
        re int tag=0;
        fp(j,1,n-1)
      if(a[j]>a[j+1]) tag=1,wri(j),pc(' '),wri(j+1),pc('\n'),swap(a[j],a[j+1]);
        if(!tag) break;
      }
    puts("-1 -1");
    return 0; 
    }
  solve(1,n);
  puts("-1 -1");
  return 0;
}

$100pts$算法

蒟蒻其实并不知道快排原理
快排的原理是，在向下分治前，先选取一个基准数，通过归并排序，把该分治区间中的小于等于其的数移到左边，大于其的数移到右边。
归并的过程中可以通过"翻转"，把左区间中的大于其的数与右区间中小于等于其的数一次交换完毕。
然后继续向下分治即可。
基准数就是选，该区间中间位置，在排序完后的$a$中对应的值。（记得把值离散化）
复杂度$O(nlog^2n)$。
很对但是想不到。。。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
ll n,a[N],b[N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il int Qsort(re int l,re int r,re ll B)
{
  if(l==r) return l+(a[l]<=B);
  re int mid=l+r>>1,p1=Qsort(l,mid,B),p2=Qsort(mid+1,r,B)-1;
  if(p1!=mid+1&&p2!=mid)
    {
      printf("%d %d\n",p1,p2);
      reverse(a+p1,a+p2+1);
    }
  return p1+(p2-mid);
}
il void solve(re int l,re int r)
{
  if(l==r) return;
  re int mid=l+r>>1;
  Qsort(l,r,b[mid]);
  solve(l,mid);solve(mid+1,r);
}
int main()
{
  n=gi();
  fp(i,1,n) b[i]=a[i]=gi()*n+i;
  sort(b+1,b+1+n);
  solve(1,n);
  puts("-1 -1");
  return 0;
}