分治与归并（数列分治）

数列分治

通过两个题目了解吧&＃xff0c;是求逆序数的&＃xff0c;就是运用分治与归的思想&＃xff0c;我自己的理解是&＃xff1a;通过把该问题分解为好多的子问题&＃xff0c;然后一次次胡归并得到答案。

题目链接&＃xff1a;https://cn.vjudge.net/contest/243680#problem/C

题意

两道题目的意思是一致的&＃xff0c;都是数列分治的模板题目。

题解

下面附两个代码&＃xff0c;一个是该题的模板code和详细的解释&＃xff08;注释&＃xff09;。另一个是学长的关于数列分治的演示代码。

Code One

#include //数列分治&＃xff08;求逆序对数目&＃xff09;。方法&＃xff1a;分治与归并。
#include
#include
#include
#include
#include
#include

Code Two(数列分治演示)

#include
typedef long long ll;
using namespace std;
const int N &＃61; 1e5&＃43;5;int a[N], ans[N];ll solve(int l, int r)
{cout <<"l &＃61; " <>1;cout <<"mid &＃61; " <mid) ans[k] &＃61; a[j&＃43;&＃43;];else if(j>r) ans[k] &＃61; a[i&＃43;&＃43;];else if(a[i]<&＃61;a[j]) ans[k] &＃61; a[i&＃43;&＃43;];else{//出现逆序对ans[k] &＃61; a[j&＃43;&＃43;];num &＃43;&＃61; mid-i&＃43;1;//B序列中大于a[j]的个数}}for(int i &＃61; 0; i <&＃61; (r-l); i &＃43;&＃43;)a[l&＃43;i] &＃61; ans[i];for(int i &＃61; 0; i <&＃61; r; i&＃43;&＃43;)printf("%d ", a[i]);puts("");cout <<"num &＃61; " <}int main()
{int n;scanf("%d", &n);for(int i &＃61; 0; i }