[BZOJ4237]稻草人(CDQ分治)

先按y排序，二分，两边递归下去，然后处理下半部分对上半部分的贡献，即左下点在下半部分，右上点在上半部分的合法矩形个数。

两个部分均按x排序，枚举右上点p，则左下点需要满足：

1.横坐标大于上半部分纵坐标比p小的点的最大横坐标k。

2.不存在下半部分点满足纵坐标在两点之间，横坐标也在两点之间。

这样，我们对上半部分维护一个纵坐标单减的单调栈，下半部分维护纵坐标单增的单调栈。

每次枚举p时，将下半部分所有横坐标小于p的点加入栈中，再在栈中二分k即可。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

 const int N=;

 ll ans;

 int n,stk1[N],stk2[N];

 struct P{ int x,y; }p[N];

 bool cmpx(const P &a,const P &b){ return a.x<b.x; }

 bool cmpy(const P &a,const P &b){ return a.y<b.y; }

 void solve(int L,int R){

     if (R<=L) return;

     sort(p+L,p+R+,cmpy); int mid=(L+R)>>;

     sort(p+L,p+mid+,cmpx); sort(p+mid+,p+R+,cmpx);

     int top1=,top2=,w=L;

     rep(i,mid+,R){

         while (top1 && p[stk1[top1]].y>p[i].y) top1--;

         stk1[++top1]=i;

         while (w<=mid && p[w].x<p[i].x){

             while (top2 && p[stk2[top2]].y<p[w].y) top2--;

             stk2[++top2]=w; w++;

         }

         int l=,r=top2,pos=-;

         while (l<=r){

             int m=(l+r)>>;

             if (p[stk2[m]].x>p[stk1[top1-]].x) pos=m,r=m-; else l=m+;

         }

         if (~pos) ans+=top2-pos+;

     }

     solve(L,mid); solve(mid+,R);

 }

 int main(){

     freopen("bzoj4237.in","r",stdin);

     freopen("bzoj4237.out","w",stdout);

     scanf("%d",&n);

     rep(i,,n) scanf("%d%d",&p[i].x,&p[i].y);

     p[]=(P){-,-}; solve(,n); printf("%lld\n",ans);

     return ;

 }

巴特西

[BZOJ4237]稻草人(CDQ分治)

最新文章

热门文章