题目描述
blablabla
样例
blablabla
using namespace std;
const int N=1e5+10;
int a[N],t[N];
long x;
long sort(int a[],int l,int r){
if(l>=r) return 0;
int mid=(l+r)/2;
sort(a,l,mid);
sort(a,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(a[i]<=a[j]) t[k]=a[i];
else{
t[k]=a[j];
x+=mid-i+1;
}
}
while(i<=mid) t[k]=a[i];
while(j<=r) t[k]=a[j];
for(int i=0,j=l;j<=r;j,i) a[j]=t[i];
return x;
}
int main(){
int n;
cin>>n;
for(int i=0;i[HTML_REMOVED]>a[i];
long counter=sort(a,0,n-1);
cout<<counter<<endl;
}
逆序对设为long型(数据量较大),同时应放在全局变量上,不放在函数里面,否则会刷新。
x+=mid-i+1,当第i个位置大于a[j]时,那么i之后到mid间的数都大于a[j].(递增排序)