题意：两两相邻的元素可以交换，问最小交换次数使得数列为升序。
思路：归并排序分治法。看到琦神又用了树状数组的方法求。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define sc(a,b) scanf("%d%d",&a,&b) #define pri(a) printf("%d\n",a) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define MM 100004 #define MN 1008 #define INF 100000007 #define eps 1e-7 using namespace std; typedef long long ll; typedef unsigned long long ULL; ll mergesort(int *a,int n) { if(n==1) return 0; int mid=n/2; ll sum=mergesort(a,mid)+mergesort(a+mid,n-mid); int *b=new int[n]; memcpy(b,a,n*sizeof(int)); for(int i1=0,i2=mid,i=0; i1