分治法简介
主要作用
在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范型。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法（归并排序、快速排序）、傅立叶变换（快速傅立叶变换）。
分治算法是一个解决复杂问题的好工具，它可以把问题分解成若干个子问题，把子问题逐个解决，再组合到一起形成大问题的答案。比如，汉诺塔问题如果采用分治算法，可以把高度为$n$的塔的问题转换成高度为n-1的塔来解决，如此重复，直至问题化简到可以很容易的处理为止。
实现
分治通过递归实现。在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
- 解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
- 合并：将各子问题的解合并为原问题的解。
递归中的问题
举例
假设当前需要求$x \times y$的值，如果我们一位一位地算，需要进行$n$次$1$位数乘$n$位数的乘法，需要进行$n$次加法。总的算起来，计算一次乘法的时间复杂度为$O(n^2)$。
现在我"学会了"分治，我设$m=\frac{1}{2}n$，那么就可以将$x,y$拆为$x=a \times 10^m + b$与$y=c \times 10^m + d $，那么$x \times y = ac \times 10^{2m} + (ad + bc) \times 10^m +bd$。
这个式子看起来很强，我们将$x,y$拆成了$a,b,c,d$，递归计算了$ac,ad,bc,bd$，最后加法合并起来。但是，这种方式的复杂度没有降低，仍是$O(n^2)$，为什么？它的复杂度计算如下：
$$T(n)=4 \times T(\frac{n}{2}) $$
将$n=1,2,4,8$带入可得最终复杂度为$n^2$。
正解
所以，这道题的正确解法为：
- 计算$ac,(a+b)(c+d),bd$
- $ac=bc$
- $ad+bc=(a+b)(c+d)-ac-bd$
- $bd=bd$
最终计算时间复杂度：
$$ T(n)=3 \times T(\frac{n}{2}) + O(n) $$
计算结果约为：
$$ O(n^{1.584}) $$
结论
分治是将问题变成小问题，每部分递归处理，最终合并得到答案。如果一个分法是有效的，意味着 递归合并比直接计算好。否则我们根本不需要分治！通常，我们可以使用“主定理”分析分治的复杂度。或者，可以展开几层看看是否符合直觉。
有时分治仅仅是把问题拆成了几个部分，而并没有降低复杂度，这种情况很容易骗过自己，请谨慎分析。
简单分治应用实例
归并排序
将待排序的数分成两半，递归排序，最后合并两个有序数组。最主要的问题在于合并。
现在你有两个有序数组，你要将它们合并成一个有序数组。假设这两个有序数组$a,b$共有$n$个数。最小的数一定在$a,b$的开头，先删掉这个数，剩下的$n-1$个数仍然在开头。最后指针不断移动，直到所有的数进入这个有序序列。
合并过程中每次会比较两个序列中较小的数，至多进行$n-1$次比较，复杂度为$O(n)$。
将整个过程带入主定理，得出归并排序算法总复杂度为$ Θ(n \log n) $
逆序对
逆序对：如果$i
对于这种问题，我们先想一种最简单的方式：进行冒泡排序，每次交换两个数，它们的逆序对数量就$-1$，所以一个复杂度为$O(n^2)$的冒泡排序可以解决这个问题。
现在考虑分治做法。每次将数组分为两半，递归数每部分的逆序对，最后数一数$i$在左边，$j$在右边的部分。如果直接暴力比较，就会出现上面提到的问题。但对于逆序对，我们可以通过归并排序来解决。归并排序会对两个有序序列中的最小数值一一比较，其中一部分我们看作为$i$，另一部分看作为$j$，因为$i$总是在$j$的左面，每当有$a_j$小于$a_i$的情况，就说明出现了一组逆序对。
二分法
二分法：对于在区间$[a,b]$上连续不断且$f(a)f(b)<0$的函数$y=f(x)$通过不断地把函数$f(x)$零点所在区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法，叫做二分法。
直接运用二分法的有两种：二分查找、二分答案。
二分查找：二分查找是一种在有序数组中查找某一特定元素的查找算法。查找过程从数组的中间元素开始：如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。解通常是唯一的，或者不存在。
使用STL来进行二分查找：
lower_bound()返回有序表里第一个大于等于给定值的指针或迭代器；upper_bound()返回有序表里第一个大于给定值的指针或迭代器；binary_search()返回给定值是否在有序表里存在。- 对于以上的STL，普通数组可以直接使用下标寻找。如
lower_bound(a+1,a+1+n,2)-a-1 - vector用法：使用迭代器。
lower_bound(a.begin(),a.end(),2) - set/map/…用法：使用专门的操作，他们的迭代器不可减。
a.lower_bound(2)
- 对于以上的STL，普通数组可以直接使用下标寻找。如
二分答案：二分答案，即通过题目中包含的单调性对答案进行二分。大多数二分答案可以看做是标准二分法套了一个奇奇怪怪的函数。解答需要使用二分答案的题目，最重要的是观察出单调性。
通常来说，题面中有，或者暗含类似于如下的最优化问题：最大值最小/最小值最大、最靠近某个值、最小的能满足条件的代价……那么通常都可以往二分答案想。
进阶分治应用实例
CDQ分治
CDQ分治是我们处理各类问题的重要武器，它的优势在于可以顶替复杂的高级数据结构，而且常数比较小；缺点在于必须离线操作。
它的具体形式多种多样，没有固定模板，其中一个典型应用如下：
三维偏序
三位偏序是CDQ分治的一个重要应用。首先说一下，什么是*维偏序：
形如$x_i 现在对于一维偏序：求$n$个$x_i$这样的点中，对于每个i求出满足$x_i 对于三维偏序，有过一句话：“一维排序，二维分治，三维数据结构”。在数逆序对的基础上，用数据结构维护$z$，按照$y$的顺序更新。时间复杂度为$O(n \log ^2 n)$，这种分治就被称为CDQ分治。 那么对于四维偏序，可以在数据结构上加$\log$，也可以分治套分治，但时间复杂度通常为$O(n \log ^3 n)$。所以在维护k维偏序（$k \ge 4$）时通常不如bitset。 对于需要回答$n$个位置上的相同类型的问题每次回答一个需要二分答案查询，且$check$需要构建一个数据结构，复杂度非常高的问题，可以采取整体二分。 思路：二分一个答案，构建数据结构并判断所有询问，递归处理二分的两边。典型复杂度是$O(n \log ^2 n)$。实现起来很像 CDQ 分治。 （待更新） 来源：洛谷：P3810 【模板】三维偏序（陌上花开） 主定理就是找出影响时间复杂度的最主要的部分。 以下是评估递归时间复杂度的主定理，例如有递归形式 $$T(n)=aT(n/b)+f(n)$$ 其中, $a≥1$和$b≥1$, 均为常数,$ f(n)$是一个确定的正函数。 在$f(n)$的三类情况下, 我们有$T(n)$的渐近估计式：k维偏序
整体二分
WQS二分
代码
平面内最近点对
三维偏序
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define LL long long
#define uLL unsigned long long
#define reg register
#define PI acos(-1.0)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
#define M 2000001
template<class T>inline void read(T &x)
{
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
}
template<class T>inline void print(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
struct Node
{
int a,b,c,ans,cnt;
}A[M],a[M];
int n,k,cnt1,cnt2,ANS[M],c[M];
bool cmp1(Node x,Node y)
{
if(x.a==y.a)
if(x.b==y.b)
return x.c<y.c;
else
return x.b<y.b;
else
return x.a<y.a;
}
bool cmp2(Node x,Node y)
{
if(x.b==y.b)
return x.c<y.c;
else
return x.b<y.b;
}
int lowbit(int x)
{
return x&-x;
}
void build(int x,int y)
{
while(x<=k)
{
c[x]+=y;
x+=lowbit(x);
}
return;
}
int search(int x)
{
int ans=0;
while(x)
{
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
void cdq(int l,int r)
{
if(l==r)
return;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
sort(a+l,a+1+mid,cmp2);
sort(a+1+mid,a+1+r,cmp2);
int j=l;
for(int i=mid+1;i<=r;i++)
{
while(a[i].b>=a[j].b&&j<=mid)
{
build(a[j].c,a[j].cnt);
j++;
}
a[i].ans+=search(a[i].c);
}
for(int i=l;i<j;i++)
{
build(a[i].c,-a[i].cnt);
}
return;
}
int main()
{
read(n),read(k);
for(int i=1;i<=n;i++)
{
read(A[i].a),read(A[i].b),read(A[i].c);
}
sort(A+1,A+1+n,cmp1);
for(int i=1;i<=n;i++)
{
cnt2++;
if(A[i].a!=A[i+1].a||A[i].b!=A[i+1].b||A[i].c!=A[i+1].c)
{
a[++cnt1].a=A[i].a;
a[cnt1].b=A[i].b;
a[cnt1].c=A[i].c;
a[cnt1].cnt=cnt2;
cnt2=0;
}
}
cdq(1,cnt1);
for(int i=1;i<=cnt1;i++)
ANS[a[i].ans+a[i].cnt-1]+=a[i].cnt;
for(int i=0;i<n;i++)
print(ANS[i]),putchar('\n');
return 0;
}
主定理
