# 洛谷 逆序对

 1234567891011121314151617181920212223242526272829303132333435363738394041 #include #include #include #include #include using namespace std; int n,arr[40005],arr_temp[40005]; int cnt; void MergeSort(int start,int end){//[start,end]     if(start==end)return;     MergeSort(start,(start+end)/2);     MergeSort((start+end)/2+1,end);     memcpy(arr_temp+start,arr+start,sizeof(int)*(end-start+1));     int ptr1=start,ptr2=(start+end)/2+1,ptr_main=start;     while(ptr1<=(start+end)/2&&ptr2<=end){         if(arr_temp[ptr1]>n;     for(int i=1;i<=n;i++)cin>>arr[i];     MergeSort(1,n);     cout<

20180730更新：又写了一遍，再贴代码：

 1234567891011121314151617181920212223242526272829303132333435363738394041 #include #include #include #include #include #include #include #include #include #include using namespace std; int n; int arr[40005]; int tmparr[40005], tmparr2[40005]; int rop = 0; void mergeSort(int l, int r) {     if (l == r)return;     int ls = l, le = (l + r) / 2, rs = (l + r) / 2 + 1, re = r;     mergeSort(ls, le);     mergeSort(rs, re);     int lp = ls, rp = rs, cp = l;     while (lp <= le && rp <= re) {         if (tmparr[lp] < tmparr[rp])tmparr2[cp++] = tmparr[lp++];         else {             tmparr2[cp++] = tmparr[rp++];             rop += le - lp +1;         }     }     for (; lp <= le; lp++)tmparr2[cp++] = tmparr[lp];     for (; rp <= re; rp++)tmparr2[cp++] = tmparr[rp];     memcpy(tmparr + l, tmparr2 + l, sizeof(int)*(r - l + 1)); } int main() {     ios::sync_with_stdio(false);     cin >> n;     for (int i = 1; i <= n; i++)cin >> arr[i];     memcpy(tmparr, arr, sizeof(arr));     mergeSort(1, n);     cout << rop; }

20200409更新：题目更新了，数据加强了。做了小小改动。

 123456789101112131415161718192021222324252627282930313233 #include #include using namespace std; long long n; long long arr[500005]; long long tmparr[500005], tmparr2[500005]; long long rop = 0; void mergeSort(long long l, long long r) {     if (l == r)return;     long long ls = l, le = (l + r) / 2, rs = (l + r) / 2 + 1, re = r;     mergeSort(ls, le);     mergeSort(rs, re);     long long lp = ls, rp = rs, cp = l;     while (lp <= le && rp <= re) {         if (tmparr[lp] <= tmparr[rp])tmparr2[cp++] = tmparr[lp++];         else {             tmparr2[cp++] = tmparr[rp++];             rop += le - lp + 1;         }     }     for (; lp <= le; lp++)tmparr2[cp++] = tmparr[lp];     for (; rp <= re; rp++)tmparr2[cp++] = tmparr[rp];     memcpy(tmparr + l, tmparr2 + l, sizeof(long long) * (r - l + 1)); } int main() {     ios::sync_with_stdio(false);     cin >> n;     for (long long i = 1; i <= n; i++)cin >> arr[i];     memcpy(tmparr, arr, sizeof(arr));     mergeSort(1, n);     cout << rop; }