CDQ 分治

前置：偏序问题

其实算不上前置，但是本篇是对这篇的补充。

CDQ 分治

如果你学过归并排序，那你肯定知道归并排序的做法是先让前后两部分有序，然后进行合并，这与 CDQ 的思想是差不多的。

CDQ 的整体仍然是分治，递归处理左右区间，但不同的是，CDQ 会考虑左区间对右区间的影响，并对于右区间或者答案进行更改与修正。

举个例子

逆序对

统计 \(i < j\)，且 \(a_i > a_j\) 的数对 \((i,j)\) 个数。

\(n \leq 5 \times 10 ^ 5\)

具体来讲，分治时使用 \(i,j\) 分别记录左（\(\left[ l,mid \right]\)）、右区间（\(\left[ mid + 1,r \right]\)）的当前位置。

当 \(a_i < a_j\) 时，对答案没有贡献，将 \(a_i\) 加入数组 \(b\) 中。

当 \(a_i > a_j\) 时，因为左右区间已经处理过了，所以现在两个区间都是有序的，所以有 \(x \in \left[ i,mid\right],a_x > a_j\)。对答案的贡献为 \(mid - i + 1\)。然后将 \(a_j\) 加入数组 \(b\)。

当遍历完左右区间后，数组 b 为有序数组，直接赋值给原区间即可。

前置中的三位偏序

三位偏序

有 $ n $ 个元素，第 $ i $ 个元素有 $ a_i,b_i,c_i$ 三个属性，设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 \(j\) 的数量。

对于 $ d \in [0, n) $，求 $ f(i) = d $ 的数量。

$ 1 \leq n \leq 10^5$。

首先排序可以消掉一维，还剩两维。

分治时使用 sort 将左右区间分别排序，又消掉一维。

最后一维使用树状数组，使用 \(i,j\) 分别记录左（\(\left[ l,mid \right]\)）、右区间（\(\left[ mid + 1,r \right]\)）的当前位置。枚举 \(j\)，对于每个 \(i\) 满足 \(b_i < b_j\)，将树状数组上 \(c_i\) 的位置 +1，这样在查找 \(c_i \leq c_j\) 时，\(i\) 的个数为树状数组上 \(c_j\) 的前缀和。即为产生的贡献。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,cnt,t,res[2000005];
struct node{
	int a,b,c,cnt,ans;
	bool operator!=(const node &x)const
	{
		return (a!=x.a || b!=x.b || c!=x.c);
	}
}h[2000005],a[2000005];
bool cmpa(node x,node y)
{
	if(x.a!=y.a) return x.a<y.a;
	if(x.b!=y.b) return x.b<y.b;
	return x.c<y.c; 
}
bool cmpb(node x,node y)
{
	if(x.b!=y.b) return x.b<y.b;
	return x.c<y.c;
}
int c[2000005];
void modify(int x,int k)
{
	for(int i=x;i<=m;i+=(i&-i))
	{
		c[i]+=k;
	}
}
int query(int x)
{
	int ans=0;
	for(int i=x;i>=1;i-=(i&-i))
	{
		ans+=c[i];
	}
	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+mid+1,cmpb);
	sort(a+mid+1,a+r+1,cmpb);
	int i=l,j=mid+1;
	while(j<=r)
	{
		while(i<=mid && a[i].b<=a[j].b)
		{
			modify(a[i].c,a[i].cnt);
			i++;
		}
		a[j].ans+=query(a[j].c);
		j++;
	}
	for(int k=l;k<i;k++) modify(a[k].c,-a[k].cnt); 
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i].a>>h[i].b>>h[i].c;
	}
	sort(h+1,h+1+n,cmpa);
	for(int i=1;i<=n;i++)
	{
		t++;
		if(h[i]!=h[i+1])
		{
			cnt++;
			a[cnt]=h[i];
			a[cnt].cnt=t;
			t=0;
		}
	}
	CDQ(1,cnt);
	for(int i=1;i<=cnt;i++)
	{
		res[a[i].cnt+a[i].ans-1]+=a[i].cnt;
	}
	for(int i=0;i<n;i++)
	{
		cout<<res[i]<<'\n';
	} 
	return 0;
}