(luogu1908)逆序对 发表于 2017-10-24 | 分类于 solution , 分治 , 归并排序 一道经典题 思路:使用归并排序的思想解决 将序列从小到大归并排序 当右边的值小于左边的值时加上左边未归并的长度 代码:12345678910111213141516171819202122232425262728293031323334353637383940#include <iostream>#include <cstdio>using namespace std;const int Mn(40005);int n;int a[Mn],t[Mn];int mg(int l,int r){ if(l==r) return 0; else { int m((l+r)>>1); int ret(0); ret += mg(l,m); ret += mg(m+1,r); int li(l),ri(m+1),j(l); while(li<=m&&ri<=r) { if(a[li]<=a[ri]) t[j++] = a[li++]; else { t[j++] = a[ri++]; ret += m-li+1; } } for(;li<=m;++li) t[j++] = a[li]; for(;ri<=r;++ri) t[j++] = a[ri]; for(int i(l);i<=r;++i) a[i] = t[i]; return ret; }}int main(){ cin >> n; for(int i(1);i<=n;++i) { scanf("%d",&a[i]); } cout << mg(1,n); return 0;}