基本思想:将序列分为 \([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];
}
标签:递归,int,分治,mid,算法,两边,排序,sim
From: https://www.cnblogs.com/includec/p/17718720.html