分治的思想

分治算法是一种很重要的算法策略，它的基本思想是将一个复杂的问题分解成更多相同或相似的子问题，所以分治算法通常以递归的方式实现。

就像之前讲的归并排序(不知道可以翻翻之前的博客),将排序的过程不断拆解，排n个数可以排两个n/2个数，看做排n/2再/2，排4段数，最后可以看做排n段长度为1的数组，在不断合并的过程中完成排序，利用归并排序和分治的思想，可以求解逆序对的问题

先附上归并排序的代码

#include<iostream>
using namespace std;
const int N = 1e5 + 9;
int a[N], b[N];
void MergeSort(int a[], int l, int r)
{
	if (l == r)return;
	int mid = (l + r) / 2;
	MergeSort(a, l, mid);
	MergeSort(a, mid + 1, r);

	int pl = l, pr = mid + 1, pb = l;
	while (pl <= mid || pr <= r)
	{
		if (pl > mid)
		{
			b[pb++] = a[pr++];
		}
		else if (pr > r)
		{
			b[pb++] = a[pl++];
		}
		else
		{
			if (a[pl] < a[pr])b[pb++] = a[pl++];
			else b[pb++] = a[pr++];
		}
	}
	for (int i = l; i <= r; i++)a[i] = b[i];
}
int main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++)cin >>a[i];
	MergeSort(a, 1, n);
	for (int i = 1; i <= n; i++)cout << a[i] << " ";
	return 0;
}

不懂逆序对的可以看看洛谷P1908 逆序对

逆序对就是对于给定的一段正整数序列，逆序对就是序列中 ai>aj且i<j 的有序对，如果角标i小于j但值ai>aj，二者相反，就是逆序对，也可看做严格单调递减，知道了逆序对，怎么用归并排序求解呢?

我们知道归并排序会将数组拆成一段一段，再不断合并，那么在合并的过程中相邻的两段是不是前一段的角标都严格小于后一段，只要前一段的值大于后一段，那么就构成了逆序对

我们看一组样例

5 4 2 6 3 1
先拆分，用|表示被拆成的一段
5|4|2|6|3|1
5于4，4与2，6与3，3与1，5与2，6与1有6对
变成 5 4 2|6 3 1
有5与3 5与1 4与3 4与1 2与1 有5对
共11对

要注意的是拆分完后，开始还原，每次只算未拆分前的两段，其余的会在后面合并的过程中算到

附上AC代码

#include<iostream>
using namespace std;
const int N = 5e5 + 5;
int a[N];
int b[N];
int n;
long long  ans = 0;
void mergesort(int l, int r)
{
	if (l == r)return;
	int mid = (l + r)>>1;
	mergesort(l, mid);
	mergesort(mid + 1, r);
    
	int p1 = l, p2 = mid + 1;
	int pos = l;
	while (p1 <= mid&&p2 <= r)
	{
		if (a[p1] <= a[p2])b[pos++] = a[p1++];
		else
		{
			b[pos++] = a[p2++];
			ans += (mid - p1 + 1);
		}
	}
	while (p1 <= mid)b[pos++] = a[p1++];
	while (p2 <= r)b[pos++] = a[p2++];
	for (int i = l; i <= r; i++)
		a[i] = b[i];
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	mergesort(1, n);
	cout << ans;
	return 0;
}

当前面一段大于后面一段时，即a[p1]>a[p2]就构成了逆序对，由于两边都是单调递增，都是取更小放入辅助数组，那么从p1开始的到mid的所有数都与a[p2]构成逆序对

再提供另一种思路和写法

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N];
int b[N];
long long mergesort(int l,int r)
{
	if(l==r)return 0;
	int mid=(l+r)/2;
    long long res=mergesort(l,mid)+mergesort(mid+1,r);
	int p1=l,p2=mid+1;
	int pos=0;
	while(p1<=mid&&p2<=r) 
	{
		if(a[p1]<=a[p2])
		{
			b[++pos]=a[p1++];
			res+=p2-mid-1;
		}
		else b[++pos]=a[p2++];
	}
	while(p1<=mid)
	{
		b[++pos]=a[p1++]; 
		res+=p2-mid-1;
	}
	while(p2<=r)b[++pos]=a[p2++];
	for(int i=l;i<=r;i++)a[i]=b[i-l+1];
	return res;
}
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
    cout<<mergesort(1,n)<<endl;
	return 0;
}

当a[p1]<=a[p2]时，那么a[p1]是不是就大于从mid+1到p2-1的所有数，就构成了逆序对，当a[p1]没放完，剩余的每一个数都与后一段的每一个数构成逆序对

可以仔细思考一下，这两种写法有何不同，有助于理解

再来看一道分治的例题[CF 1385D]a-Good string

这个问题其实就是将判断a-string变成判断b-string,并将字符串长度减半的过程，通过不断转换，直到长度为1，返回要改变的次数

附上AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
char a[N];
int n;
int solve(int l,int r,char x)
{
	if(l==r)
	{
		if(x==a[l])return 0;
		else return 1;
	}
	int y1=0,y2=0;
	int mid=(l+r)>>1;
	for(int i=l;i<=mid;i++)if(a[i]!=x)y1++;
	for(int i=mid+1;i<=r;i++)if(a[i]!=x)y2++;
	return min(y1+solve(mid+1,r,x+1),y2+solve(l,mid,x+1));
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;cin>>t;
	while(t--)
	{
	   cin>>n;
	   for(int i=1;i<=n;i++)cin>>a[i];
	   cout<<solve(1,n,'a')<<endl;
	}
	return 0;
}

 每次看一下是将左边全边x代价下还是右边变x代价下，然后向下递归

最后再看一道例题洛谷P1429 平面最近点对（加强版）

对于这个题，输入每个点，可以按照x从小到 大对每个点进行排序可以对所有的点进行分治，将大的区间段分成一段一段小的区间段，当分到区间段只有一个点时，返回一个很大的值，表示没有可用的距离，开始返回后，每一段可以看做由两小段拼接而成，它的最近距离d是这两小段的d与两小段之间的点可能成为最近的更小值，然后不断返回区间段的d，找到最小的d

给个图解

假设分成的一段是有p6,p7,p8,p9,它可看作由p6,p7 与p8,p9两段拼接而成它都d就是这两段d的更小值后两端之间的点的距离如p7,p8

以下附上AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct Node{
	double x,y;
	bool operator<(const Node &A) const{
	   return x<A.x;
	}
}a[N],c[N];
double solve(int l,int r)
{
	if(l==r)return 1e11;
	int mid=(l+r)>>1;
	double d=min(solve(l,mid),solve(mid+1,r));
	int cnt=0;
	for(int i=l;i<=r;i++)
	{
		if(abs(a[i].x-a[mid].x)<d)
		{
			c[++cnt].x=a[i].y,c[cnt].y=a[i].x;
		}
	}
	sort(c+1,c+1+cnt);
	for(int i=1;i<=cnt;i++)
	{
		for(int j=i+1;j<=cnt&&c[j].x-c[i].x<d;j++)
		{
			d=min(d,sqrt((c[i].x-c[j].x)*(c[i].x-c[j].x)+(c[i].y-c[j].y)*(c[i].y-c[j].y)));
		}
	}
	return d;
}
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	sort(a+1,a+1+n);
	printf("%.4lf",solve(1,n));
	return 0;
}

在求d的过程中利用了一些小技巧，翻转下x,y不影响距离，所有可疑点按y升序排列(因为x之间的距离都小于d）所以y之间的距离也要小与d，剪去不必要的部分

欧克了