逆序对与归并排序

逆序对的定义是 对于ia[j]我们称 a[i]和a[j]是一对逆序对

如何求逆序对个数，归并排序或者线段树

归并排序方法 代码都是没测试过，不知道会不会报错...

 1 int a[N],b[N];//a是原数组，b是辅助数组，到时候复制回原数组 
 2 int ans=0;
 3 void mergesort(int l,int r)
 4 {
 5     
 6     if(l>=r)return;
 7     int mid=l+r>>1;
 8     mergesort(l,mid);
 9     mergesort(mid+1,r);
10     int pl=l,pr=mid+1,p=l;
11     while(pl<=mid&&pr<=r)
12     {
13         if(pl<=pr)b[p++]=a[pl++];
14         else 
15         {
16             ans+=mid-pl+1;
17             b[p++]=a[pr++];        
18         }
19     }    
20     while(pl<=mid)b[p++]=a[pl++];
21     while(pr<=r)b[p++]=a[pr++];
22     for(int i=l;i<=r;i++)a[i]=b[i];    
23  } 

线段树就是按值域建树，从数组后开始查询有多少个比当前元素小的数，即query(0,i-1),然后让a[i]这个节点++；

好久没写线段树了，不知道有没有错呢...

 1 void update(int x)
 2 {
 3     sum[x]=sum[ls]+sum[rs];
 4 }
 5 void build(int l,int r,int x)
 6 {
 7     if(l==r)return;
 8     int mid=l+r>>1;
 9     build(l,mid,ls);
10     build(mid+1,r,rs);
11 }
12 void modify(int l,int r,int A,int B,int x)
13 {
14     if(A<=l&&B>=r)
15     {
16         sum[x]++;
17         return;
18     }
19     int mid=l+r>>1;
20     if(A<=mid)modify(l,mid,A,B,ls);
21     if(mid1,r,A,B,rs);
22     update(x);
23 }
24 int query(int l,int r,int A,int B,int x)
25 {
26     if(A<=l&&r<=B)return sum[x];
27     int mid=l+r>>1,ans=0;
28     if(A<=mid)ans+=query(l,mid,A,B,ls);
29     if(mid1,r,A,B,rs);
30     return ans;
31 }

最后就是今天看到的题，求一个乱序排列，最少交换几次能变升序排列，每次只能相邻交换，答案是逆序对数；

证明，数学归纳法；n为逆序对数

当n=1时显然成立；

假设n=k时结论成立；

当n=k+1时 我们选择在k对逆序对的基础上，在后面造一对逆序对变成k+1对，且对全局无影响；

由上述结论知道对于k+1对逆序对，我们用1步还原后面逆序对而使得全体影响只剩K对逆序对，对k结论成立；从而K+1成立证毕！