#include<iostream> using namespace std; const int N = 1e6+10; int n; long long cnt=0; int q[N],tmp[N]; void count(int q[],int l,int r) { if(l>=r)return ; int mid = (l+r)>>1; count(q,l,mid); count(q,mid+1,r); int k=0,i=l,j=mid+1; while(i<=mid && j<=r) { if(q[i]<=q[j]) { tmp[k++]=q[i++]; //cnt++; } else { tmp[k++]=q[j++]; cnt += (mid - i + 1); //这里是重点 } } while(i<=mid) tmp[k++]=q[i++]; while(j<=r) tmp[k++]=q[j++]; for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j]; } int main() { cin>>n; for(int i=0;i<n;i++) cin>>q[i]; count(q,0,n-1); cout<<cnt; return 0; }
数组a中的i ~ mid的数组是递增数组, 触发条件是a[i] > a[j],所以i~mid中的数字都比当前a[j]大,所以左边i ~ mid的数组中有 mid – i + 1个数比a[j] 大。
原创文章,作者:3628473679,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/244348.html