题目描述
关于数据量上100000后出错,数据类型定为long int
样例
C++ 代码
#include <iostream>
using namespace std;
const int N=100010;
long int n,q[N],t[N],sum=0;
void mergesort(long int q[],long int l,long int r){
if(l>=r)return ;
long int mid=l+r>>1;
mergesort(q,l,mid);
mergesort(q,mid+1,r);
long int index1=l,index2=mid+1,k=0;
while(index1<=mid&&index2<=r){
if(q[index1]<=q[index2])t[k++]=q[index1++];
else{
t[k++]=q[index2++];
sum+=mid-index1+1;
}
}
while(index1<=mid){
t[k++]=q[index1++];
}
while(index2<=r)t[k++]=q[index2++];
for(long int j=l,i=0;j<=r;i++,j++){
q[j]=t[i];
}
}
int main(){
cin>>n;
for(long int i=0;i<n;i++)cin>>q[i];
mergesort(q,0,n-1);
cout<<sum;
return 0;
}