Article From:https://www.cnblogs.com/yanshannan/p/9689423.html

https://www.zybuluo.com/ysner/note/1289967

surface”

Define “reverse sort”: each operation is interval.\([l,r]\)All the numbers are reversed.\(swap(a[l],a[r])+swap(a[l+1],a[r-1])+…\)
The cost of each operation is\(r-l+1\)
Give a sequence\(a\),Sort it by “flip sort” and control the cost.\(2*10^7\)Within.

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

\(noip\_T2\)Difficulty.

>\(60pts\)algorithm

Think carefully, “flip” this condition is disgusting.
Can not “flip”? It can only exchange two adjacent ones.

Scavenging sequence\(n\)Each time, only two adjacent numbers are exchanged.
In this way, each exchange corresponds to eliminating a reverse order, and the complexity is controllable.
The number of times is the most.\((n-1)*[(n-1)-1]/2\leq1.25*10^7\)
But I don’t know what this sort of name is.

Complexity\(O(n^2)\)
The code is in the next file.

\(85pts\)algorithm

This is kind of funny.
Direct merge sort is OK.
Take the left side after each merge.\(1\)Interval and right\(0\)The interval will be together and flip.
Complexity\(O(nlogn)\)
Paste the code.

#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\)algorithm

He did not know the principle of fast displacement.
The principle of fast queuing is that before dividing and conquering, a benchmark number is selected and the number less than or equal to it in the divide and conquer interval is moved to the left and the number greater than it is moved to the right by merging and sorting.
In the process of merging, the number larger than it in the left interval can be exchanged with the number less than or equal to it in the right interval by “flipping”.
Then continue to divide down.
The base number is the selection, the middle position of the interval, after sorting.\(a\)The corresponding value in. (remember to discretize values)
Complexity\(O(nlog^2n)\)
Yes, but I didn’t think so.

#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;
}
Link of this Article: [noi.ac_D1T2]sort

Leave a Reply

Your email address will not be published. Required fields are marked *