P1908 逆序对

代码如下

#include <cstdio>
using namespace std;
long long a[500002],t[500002];
long long cnt=0;
void merge(int l,int m,int r){
  int i=l,j=m+1,k=l;
  while(i<=m && j<=r){
    if(a[j]>a[i]){
      t[k++]=a[i++];
    }else{
      t[k++]=a[j++];
      cnt+=m-i+1;
    }
  }while(i<=m){
    t[k++]=a[i++];
  }while(j<=r){
    t[k++]=a[j++];
  }for(int s=l;s<=r;s++){
    a[s]=t[s];
  }
}void m_sort(int l,int r){
  if(l>=r){
    return;
  }int m=l+r>>1;
  m_sort(l,m);
  m_sort(m+1,r);
  merge(l,m,r);
}int main(){
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
  }m_sort(1,n);
  printf("%lld",cnt);
}

只有30分 在线求救 急急急急急急