求大神指点!

使用归并做的逆序对为什么会超时啊……有没有大神帮小弟看一下……
###------------------------------分割线--------------------------------------------
#include <iostream>
#include <cstring>
using namespace std;
long c[100001],d[100001];
long s=0;
void Qsort(long l,long r)
{
long i,j,k,mid;
mid=c[(l+r)/2];
i=l; j=r;
while (i<=j){
while (c[i]<mid) i++;
while (c[j]>mid) j--;
if (i<=j){
k=c[i];
c[i]=c[j];
c[j]=k;
k=d[i];
d[i]=d[j];
d[j]=k;
i++;
j--;
}

}
if (l<j) Qsort(l,j);
if (i<r) Qsort(i,r);
}
void sort(long l,long mid,long r)
{
long i,j,k;
for (i=l;i<=mid;i++)
for (j=r;j>=mid+1;j--){
if (c[i]>c[j]){
s=(s+j-mid)%99999997;
break;
}
}
i=l;
j=mid+1;
for (k=l;k<=r;k++){
if ((c[i]<c[j] && i<=mid) || (j>r)){
d[k]=c[i];
i++;
}else {
d[k]=c[j];
j++;
}
}
for (i=l;i<=r;i++)
c[i]=d[i];
}
void merge(long l,long r)
{
long mid;
mid=(l+r)/2;
if (l<mid) merge(l,mid);
if (mid+1<r) merge(mid+1,r);
sort(l,mid,r);
}
main()
{
long a1[100001],a2[100001],b1[100001],b2[100001],i,j,n;
cin>>n;
for (i=1;i<=n;i++){
cin>>a1[i];
b1[i]=b2[i]=i;
}
for (i=1;i<=n;i++) cin>>a2[i];
memcpy(c,a1,sizeof(a1)); memcpy(d,b1,sizeof(b1));
Qsort(1,n);
memcpy(a1,c,sizeof(a1)); memcpy(b1,d,sizeof(b1));
memcpy(c,a2,sizeof(a2)); memcpy(d,b2,sizeof(b2));
Qsort(1,n);
memcpy(a2,c,sizeof(a2)); memcpy(b2,d,sizeof(b1));
for (i=1;i<=n;i++){
a1[b1[i]]=i; a2[b2[i]]=i;
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (a1[i]==a2[j]){ a1[i]=j; break;}
memcpy(c,a1,sizeof(c));
merge(1,n);
cout<<s;
}

4 条评论

  • 1

信息

ID
1842
难度
7
分类
(无)
标签
递交数
5085
已通过
1102
通过率
22%
被复制
10
上传者