BZOJ2769 : YY的快速排序

时间：2022-04-07 09:54:31

将数字离散化并去重，则对于一对逆序对$i<j$,$a_i>a_j$,贡献为$\frac{2}{a_i-a_j+1}$，因此只要对于每个差值统计出对应的逆序对个数即可。

将序列分块，块内平方暴力，块与块之间做FFT即可。

时间复杂度$O(n\sqrt{n\log n})$。

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=33000;

int n,m,x,i,j,k,pos[N],a[N],b[N],at[N],st[N],en[N],f[N];double ans;

struct comp{

  double r,i;comp(double _r=0,double _i=0){r=_r;i=_i;}

  comp operator+(const comp&x){return comp(r+x.r,i+x.i);}

  comp operator-(const comp&x){return comp(r-x.r,i-x.i);}

  comp operator*(const comp&x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}

  comp conj(){return comp(r,-i);}

}A[N],B[N];

const double pi=acos(-1.0);

void FFT(comp a[],int n,int t){

  for(int i=1;i<n;i++)if(i<pos[i])swap(a[i],a[pos[i]]);

  for(int d=0;(1<<d)<n;d++){

    int m=1<<d,m2=m<<1;

    double o=pi*2/m2*t;comp _w(cos(o),sin(o));

    for(int i=0;i<n;i+=m2){

      comp w(1,0);

      for(int j=0;j<m;j++){

        comp&A=a[i+j+m],&B=a[i+j],t=w*A;

        A=B-t;B=B+t;w=w*_w;

      }

    }

  }

  if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;

}

inline int lower(int x){

  int l=1,r=m,mid,t;

  while(l<=r)if(b[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;

  return t;

}

int main(){

  scanf("%d",&n);

  for(i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];

  sort(b+1,b+n+1);

  for(i=1;i<=n;i++)if(i==1||b[i]!=b[i-1])b[++m]=b[i];

  for(i=1;i<=n;i++)a[i]=lower(a[i]);

  for(i=1;i<=n;i++)at[i]=(i-1)/1500+1;

  for(i=1;i<=n;i++)en[at[i]]=i;

  for(i=n;i;i--)st[at[i]]=i;

  for(k=1;k<=m;k<<=1);k<<=1;

  j=__builtin_ctz(k)-1;

  for(i=0;i<k;i++)pos[i]=pos[i>>1]>>1|((i&1)<<j);

  for(x=1;x<=at[n];x++){

    for(i=st[x];i<=en[x];i++)for(j=i+1;j<=en[x];j++)if(a[i]>a[j])f[a[i]+m-a[j]]++;

    if(x==1)continue;

    for(i=0;i<k;i++)A[i]=comp();

    for(i=st[x]-1;i;i--)A[a[i]].r+=1.0;

    for(i=st[x];i<=en[x];i++)A[m-a[i]].i+=1.0;

    FFT(A,k,1);

    for(i=0;i<k;i++){

      j=(k-i)&(k-1);

      B[i]=B[i]+A[i]*A[i]-(A[j]*A[j]).conj();

    }

  }

  for(i=0;i<k;i++)B[i]=B[i]*comp(0,-0.25);

  FFT(B,k,-1);

  for(i=1;i<m;i++)ans+=2.0/(i+1)*(f[i+m]+int(B[i+m].r+0.5));

  return printf("%.6f",ans),0;

}

　　

相关文章