CDQ分治详解

解决问题：

这类问题一般是给你一个长度为 n 的序列，然后让你统计有一些特性的点对(i,j)有多少个，又或者说是找到一对点(i,j)使得一些函数的值最大之类的问题

算法流程：

1. 找到当前序列中点mid

2. 将所有的点分为三类

第一种是(1leq ileq mid 1leq jleq mid)

第二种是(1leq mid+1 mid+1leq jleq n)

第三种是(mid+1leq ileq n mid+1leq jleq n)

3. 将(1,n)序列分为两部分(1,mid)和(mid+1,n)

会发现第一类点和第三类点分别被完全包含在两个序列

考虑如何求解第二类点，结合一下题来说明一下吧

经典问题

三维偏序：给定一个序列，每个点有两个性质((a_i,b_i))，求这个序列中有多少个点对满足(i < j，a_i < a_j，b_i < b_j)

假设我们现在在solve(l,r)，而且现在我们已经求出了solve(l,mid)和solve(mid+1,r)

那么我们现在就是统计(lleq ileq mid，mid+1leq jleq r)的点对(i,j)满足(i < j，a_i < a_j，b_i < b_j)

然后我们发现(i < j)这个条件没有用了，因为一定满足

剩下两个条件我们可以吧(l,mid)和(mid+1,r)的点分别按照a排序，然后在(mid+1,r)中枚举j，把所有的(a_i < a_j)全部插入到数据结构中

因为a已经排好序了，所以对于后一个的j，满足前一个j的(a_i)一定满足后一个j

核心代码：

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+mi+1,cmpy),sort(a+mid+1,a+r+1,cmpy);
	int j = l;
	for (int i = mid+1;i <= r;i++){
		while (a[j].y <= a[i].y&&j <= mid) add(a[j].z,a[j].w),j++;
		a[i].ans += query(a[i].z;)
	}
	for (int i = l;i < j;i++) add(a[i].z,-a[i].w);
}