●BZOJ 4237 稻草人

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=4237

题解：

CDQ分治，单调栈

把所有点先按x从小到大排序，然后去CDQ分治y坐标。
在分治的每一层，把所有的点平均地分为上下两个部分，
然后计算下面的点可以对上面的每个点分别造成多少的贡献：
(也就是说，对于上面的每个点，以它作为右上角，看下面的点中有多少个合法的左下角)
假设现在枚举到了上面的第k个点，
如果下面存在这样两个点i,j满足Xi<Xj且Yi<Yj，那么必然i点无法作为一个合法的左下角。
所以我们对下面的X坐标小于Xk的点维护一个Y单调下降的栈，
那么现在是不是栈的大小就是对k点而言，下面合法的左下角的点数。
答案是否定的，因为k点同样会受到上面的点对它的影响，
考虑在上面部分存在这么一个点w,满足Xw<Xk且Yw<Yk，
那么必然在下面部分的合法的左下角的x坐标要大于Xw。
所以具体做法就是，对上面的点维护一个单调上升的栈，对下面的点维护一个单调下降的栈，
然后对于每个上面的点，在下面的点维护出来的单减栈中去二分出合法的左下角的个数，然后累加进答案。
复杂度$O(Nlog^2N)$

代码：

#include<bits/stdc++.h>

#define MAXN 200005

using namespace std;

long long ANS;

int N,intop,detop;

int A[MAXN],instk[MAXN],destk[MAXN];

struct Point{

	int x,y;

	bool operator <(const Point &rtm) const{

		return x<rtm.x;

	}

}P[MAXN];

int binary(int l,int r,int v){

	static int mid,ret; ret=r+1;

	while(l<=r){

		mid=(l+r)>>1;

		if(destk[mid]>v) ret=mid,r=mid-1;

		else l=mid+1;

	}

	return ret;

}

void CDQ(int l,int r){

	static int tmpl[MAXN],tmpr[MAXN];

	if(l==r) return;

	int mid=(l+r)>>1,bl=l-1,br=mid,p;

	intop=detop=0;

	for(int i=l;i<=r;i++){

		if(A[i]>mid){

			while(intop&&A[instk[intop]]>A[i]) intop--;

			instk[++intop]=i; tmpr[++br]=A[i];

			p=binary(1,detop,instk[intop-1]); ANS+=detop-p+1;

		}

		else{

			while(detop&&A[destk[detop]]<A[i]) detop--;

			destk[++detop]=i; tmpl[++bl]=A[i];

		}

	}

	for(int i=l;i<=mid;i++) A[i]=tmpl[i];

	for(int i=mid+1;i<=r;i++) A[i]=tmpr[i];

	CDQ(l,mid); CDQ(mid+1,r);

}

int main(){

	static int tmpy[MAXN];

	scanf("%d",&N);

	for(int i=1;i<=N;i++){

		scanf("%d%d",&P[i].x,&P[i].y);

		tmpy[i]=P[i].y;

	}

	sort(P+1,P+N+1); sort(tmpy+1,tmpy+N+1);

	for(int i=1;i<=N;i++) A[i]=lower_bound(tmpy+1,tmpy+N+1,P[i].y)-tmpy;

	CDQ(1,N);

	printf("%lld\n",ANS);

	return 0;

}