rt

本人思路和题解略有不同。

我首先先按y来排序，这样的话每个矩形的就在上下找。

l到mid是分界线下方的点，mid+1到r是分界线上方的点。

我先把两个区间按照x坐标排序

令i为l到mid中的一个下标，j为mid+1到r的一个下标。

不一样的地方来了，我考虑上下方都维护一个y坐标单调下降的单调栈。每次用i尽量往后走，但是保证x坐标小于目前j。

将i更新后，我再看如果j的y坐标比单调栈的top的y坐标还要大的话，我就减掉了单调栈top的不合法贡献，再把j更新进单调栈里。

结果有wa有ac：this

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,ans;
struct node{
	int x,y;
}a[N];
bool cmp2(node x,node y)
{
	return x.x<y.x;
}
bool cmp1(node x,node y)
{
	return x.y<y.y;
}
int st1[N],tp1,st2[N],tp2;
int bs(int val)
{
	int l=1,r=tp1,ret=0;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(a[st1[mid]].x<=val)
			ret=mid,l=mid+1;
		else
			r=mid-1;
	}
	return ret;
}
void cdq(int l,int r)
{
	if(l==r)
		return;
	int mid=l+r>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	sort(a+l,a+mid+1,cmp2);
	sort(a+mid+1,a+r+1,cmp2);//按x排序 
	int i=l,j=mid+1;
	tp1=tp2=0;
	for(j;j<=r;j++)
	{
		while(i<=mid && a[i].x<=a[j].x)
		{
			while(tp1 && a[st1[tp1]].y<=a[i].y)
				tp1--;
			st1[++tp1]=i++;//更新i点 
		}
		if(a[st2[tp2]].y<=a[j].y && tp2)
			ans-=bs(a[st2[tp2]].x);//减去不合法的贡献 
		while(tp2 && a[st2[tp2]].y<=a[j].y)
			tp2--;
		st2[++tp2]=j;//更新j点 
		ans+=tp1;//更新答案 
	}
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&a[i].x,&a[i].y);
	sort(a+1,a+1+n,cmp1);
	cdq(1,n);
	printf("%lld\n",ans);
	return 0;
}