分治算法

发布时间 2023-09-20 22:55:21作者: include_c

基本思想:将序列分为 \([l,mid]\)\([mid+1,r]\),然后递归两边,同时再计算 \([l,mid]\)\([mid+1,r]\) 影响所产生的答案(满足单调性的话一般使用走指针)。

二维偏序

首先将所有元素按 \(x,y\) 排序。

然后递归两边,随后用两个指针 \(i\)\(j\)\(i\)\(l\)\(mid\)\(j\)\(mid+1\)\(r\),当 \(y_i>y_j\),说明 \(l\sim i-1\) 的点都不超过 \(j\),于是 \(ans_j\) 累加 \(i-l\),然后 \(j\) 后移一位;如果不是,那么我们的 \(i\) 往后移动一位。

这么做会有一个问题,我们的两边都应该按 \(y\) 排序,才能满足 \(y\) 的单调性,然而我们却按 \(x\) 排序,所以在统计完后重构 \(l\sim r\) 即可。

void f(int l,int r){
	if(l==r) return ;
	int m=(l+r)/2,i=l,j=m+1,c=l;
	f(l,m);f(m+1,r);
	while(i<=m||j<=r){
		if(j>r||(i<=m&&a[i].y<=a[j].y))
			b[c++]=a[i++];//类似于归并排序
		else ans[a[j].id]+=i-l,b[c++]=a[j++];
	}
	for(int i=l;i<=r;i++)a[i]=b[i];
}