本文主要是介绍[BZOJ 4237]稻草人：CDQ分治，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击这里查看原题
这个CDQ分治需要首先按Y坐标排序，然后每个递归处理的区间内按X坐标排序。每次从右区间加入一个点则将左区间所有X坐标小于该点的点加入，维护两个单调栈，左区间的是Y坐标递减的栈，右区间是Y坐标单调递增的栈。这样每次加入右区间的点时答案就是
（左区间的栈中的元素数-左栈中Y坐标小于右区间上一个点的Y坐标的点数）
有点拗口，具体看代码，用二分搜索得到左栈中Y坐标小于右区间上一个点的Y坐标的点数
/*
User:Small
Language:C++
Problem No.:4237
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const int M=2e5+5;
int n,p[M],q[M],tp1,tp2;
ll ans;
struct no{int x,y;
}a[M],b[M];
bool cmp(no a,no b){return a.y<b.y;
}
int find(int x,int l,int r){while(l+1<r){int mid=(l+r)>>1;if(a[q[mid]].x<x) l=mid;else r=mid;}return l;
}
void solve(int l,int r){if(l==r) return;int mid=l+r>>1;solve(l,mid);solve(mid+1,r);int l1=l,i,j,now=l;tp1=tp2=0; for(i=mid+1;i<=r;i++){while(tp1&&a[i].y<a[p[tp1]].y) tp1--;p[++tp1]=i;for(;l1<=mid&&a[l1].x<a[i].x;l1++){while(tp2&&a[l1].y>a[q[tp2]].y) tp2--;q[++tp2]=l1;}ans+=tp2-find(a[p[tp1-1]].x,0,tp2+1);}i=l,j=mid+1;while(i<=mid&&j<=r){if(a[i].x<a[j].x) b[now++]=a[i++];else b[now++]=a[j++];}while(i<=mid) b[now++]=a[i++];while(j<=r) b[now++]=a[j++];for(i=l;i<=r;i++) a[i]=b[i];
}
int main(){freopen("data.in","r",stdin);//scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);sort(a+1,a+n+1,cmp);solve(1,n);printf("%lld\n",ans);return 0;
}这篇关于[BZOJ 4237]稻草人：CDQ分治的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
