歸并排序

主要利用分治思想，時間復雜度O(nlogn)

原理

• 1.對數列不斷等長拆分，直到一個數的長度。
• 2.回溯時，按升序合并左右兩段。
• 3.重復以上兩個過程，直到遞歸結束。

合并
1.i，j分別指向a的左右段起點，k指向b的起點。
2.枚舉a數組，如果左數<=右數，把左數放入b數組，否則把右數放入b數組。
3.把左段或右段剩余的數放入b數組。
4.把b數組的當前段復制回a數組。

void msort(int l,int r)
{if(l==r)return ;int mid=l+r>>1;msort(l,mid);msort(mid+1,r);//拆分int i=l,j=mid+1,k=l;//合并while(i<=mid&&j<=r){if(a[i]<=a[j])b[k++]=a[i++];else b[k++]=a[j++];}while(i<=mid)b[k++]=a[i++];while(j<=r)b[k++]=a[j++];for(int i=l;i<=r;i++)a[i]=b[i];
}

逆序對

題目來源：P1908逆序對

題目描述

貓貓 TOM 和小老鼠 JERRY 最近又較量上了，但是畢竟都是成年人，他們已經不喜歡再玩那種你追我趕的游戲，現在他們喜歡玩統計。

最近，TOM 老貓查閱到一個人類稱之為“逆序對”的東西，這東西是這樣定義的：對于給定的一段正整數序列，逆序對就是序列中 $a_i>a_j$ 且 $i<j$ 的有序對。知道這概念后，他們就比賽誰先算出給定的一段正整數序列中逆序對的數目。注意序列中可能有重復數字。

Update：數據已加強。

輸入格式

第一行，一個數 $n$，表示序列中有 $n$ 個數。

第二行 $n$ 個數，表示給定的序列。序列中每個數字不超過 $10^9$。

輸出格式

輸出序列中逆序對的數目。
輸入 #1

6
5 4 2 6 3 1

輸出 #1

11

說明/提示

對于 $25\%$ 的數據，$n\le 2500$。

對于 $50\%$ 的數據，$n\le 4\times 10^4$。

對于所有數據，$1\le n\le 5\times 10^5$。

請使用較快的輸入輸出。

應該不會有人 $O(n^2)$ 過 50 萬吧 —— 2018.8 chen_zhe。
解題思路
這題就是歸并排序思想的板子題，我們可以在對這組數據進行歸并排序的時候，每當從右段取數時統計逆序對的數目。即res+=mid-i+1;

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6;
int n,a[N],b[N],res;
void msort(int l,int r)
{if(l==r)return ;int mid=l+r>>1;msort(l,mid);msort(mid+1,r);//拆分int i=l,j=mid+1,k=l;//合并while(i<=mid&&j<=r){if(a[i]<=a[j])b[k++]=a[i++];else b[k++]=a[j++],res+=mid-i+1;//關鍵一步！}while(i<=mid)b[k++]=a[i++];while(j<=r)b[k++]=a[j++];for(int i=l;i<=r;i++)a[i]=b[i];
}
signed main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];msort(1,n);cout<<res<<endl;return 0;
}