loj#2880. JOISC 2014 稻草人

搞了很久，题解区有线段树爆改pushup高妙做法

说下cdq分治

先将点都按横坐标从小到大排序，cdq分治，那我们现在只需要考虑分治过程中\([l,mid]\)和\([mid+1,r]\)互相形成的合法点对，显然左边的横坐标都小于右边的横坐标。能够发现，如果右边有一个点插在一对本来合法的点之间，那么那对合法的就非法了，于是按y从大到小排序，每次把大于新来的点的横坐标的点就删掉，贡献不了答案。

然后左边的怎么办，显然同理，有一点插在一对本来合法的点之间，那么就贡献-1。假设当前扫描到点\(i\)，找到前面的点在自己右边的点\(j\)，计算出点\(j\)能和右半边构成贡献的结果，这个东西能二分算出，然后减掉就行了，单调栈维护上面两个东西

写到这里感觉代码最好懂：

#include<bits/stdc++.h>
#define vd void 
#define MAXN 200005
int gi(){
	char c;int x=0,f=0;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))x=(x*10)+(c^48),c=getchar();
	return f?-x:x;
}
struct node{
	int x,y;
}q[MAXN];
int n,st1[MAXN],st2[MAXN],top1,top2;
long long ans=0;
int calc(int yy){
	int l=0,r=top2+1;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(q[st2[mid]].y>yy)l=mid;
		else r=mid;
	}
	return l;
}
vd cdq(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq(l,mid),cdq(mid+1,r);
	std::sort(q+l,q+mid+1,[&](node a,node b){return a.y>b.y;});
	std::sort(q+mid+1,q+r+1,[&](node a,node b){return a.y>b.y;});
	int j=mid+1;top1=top2=0;
	for(int i=l;i<=mid;i++){
		while(j<=r&&q[i].y<q[j].y){
			while(top2&&q[st2[top2]].x>q[j].x)--top2;
			st2[++top2]=j++;
		}
		ans+=top2;
		while(top1&&q[st1[top1]].x<q[i].x)--top1;
		if(top1)ans-=calc(q[st1[top1]].y);
		st1[++top1]=i;
	}
}
int main(){
	n=gi();
	for(int i=1;i<=n;i++)q[i].x=gi(),q[i].y=gi();
	std::sort(q+1,q+n+1,[&](node a,node b){return a.x<b.x;});
	cdq(1,n);
	printf("%lld\n",ans);
	return 0;
}