【题解】bzoj4237 稻草人

题目传送门

前置知识

cdq分治,单调栈,二分


定义一个点的贡献为以该点为右上角的合法矩形个数

我们先考虑固定矩形的右上端点i
那么能和该右上端点i组成合法矩形的一定是下图这样的

黑点是合法的,蓝点是非法的
对i有贡献的点一定是x递减y递增的
我们可以把这个东西用一个单调栈来维护
记该单调栈为s1

对于一堆的右上端点,我们考虑维护一个x递增,y递增的单调栈s2
那么当一个点加进单调栈中时,可能会pop掉一些点
操作完后该点的答案应该是我们维护的s1中所有y值大于等于s2中的第二个点的y值且小于等于该点y值的点数
这个可以二分一下得到
这一步的原因是会被s2中的第二个点挡住一部分s1中的点,如下图
黑点为s2中的点,蓝点为s1中的点
红色区域的蓝点是无法给右上角黑点贡献的

总答案即每个点答案之和

但这个根本没法直接维护,我们考虑cdq分治
将所有点按x从小到大排序,进cdq分治,对y归并排序
每一层只计算左半边的点对右半边的点产生的贡献
在归并y的同时,维护s1和s2
方法如上述
由于对于每一个i点,所有x小于xix_i的点都会在cdq中被考虑是否对i有贡献,故计算的答案是不重不漏的

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
struct point{
	int x,y;
}a[maxn],b[maxn],st1[maxn],st2[maxn];
long long ANS=0;
int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*y;
}
bool cmp(point p,point q){
	return p.x<q.x;
}
long long search(int tp,int y){
	int l=0,r=tp+1;
	while(l+1<r){
		int mid=l+((r-l)>>1);
		if(st1[mid].y>=y)
			r=mid;
		else
			l=mid;
	}
	return tp-r+1;
}
void merge_sort(int l,int r){
	int mid=l+((r-l)>>1);
	int p=l,q=mid+1,len=l,tp1=0,tp2=0;
	while(p<=mid&&q<=r){
		if(a[p].y<=a[q].y){
			while(tp1>=1&&st1[tp1].x<a[p].x)tp1--;
			st1[++tp1]=a[p];
			b[len++]=a[p++];
		}
		else{
			while(tp2>=1&&st2[tp2].x>a[q].x)tp2--;
			st2[++tp2]=a[q];
			ANS+=search(tp1,st2[tp2-1].y);
			b[len++]=a[q++];
		}
	}
	while(p<=mid)b[len++]=a[p++];
	while(q<=r){
		while(tp2>=1&&st2[tp2].x>a[q].x)tp2--;
		st2[++tp2]=a[q];
		ANS+=search(tp1,st2[tp2-1].y);
		b[len++]=a[q++];
	}
	for(int i=l;i<=r;i++)a[i]=b[i];
	return ;
}
void cdq(int l,int r){
	if(l==r)return ;
	int mid=l+((r-l)>>1);
	cdq(l,mid);
	cdq(mid+1,r);
	merge_sort(l,r);
	return ;
}
int main(){
	int n;
	n=read();
	for(int i=1;i<=n;i++){
		a[i].x=read();
		a[i].y=read();
	}
	sort(a+1,a+n+1,cmp);
	cdq(1,n);
	printf("%lld\n",ANS);
	return 0;
}