题意

平面上存在 $n$ 个点，求满足 $x_i<x_j\wedge y_i<y_j$ 且 $i,j$ 两点围成的矩形内不存在其余点的点对数量。

思路

先对 $x,y$ 离散化，考虑 cdq 分治。

先将点按照 $x$ 排序，假设当前分治区间为 $[l,r]$，计算 $[l,mid]$ 对于 $[mid+1,r]$ 的贡献，由于事先排过序，左区间点的 $x$ 一定小于右区间，再考虑第二维 $y$ 的限制，不妨对左右分别按照 $y$ 排序，那么枚举右区间的点，加入左区间中 $y_i<y_j$ 的点即可。

再考虑第三个限制，对于左区间的点，可以用单调栈维护，当加入一个点时，弹出其左下角所有点，这些点一定是没有贡献的，然后按这个思路写了一个代码，发现样例都过不了，因为只考虑了左边点出现在矩形中的影响，而没有考虑右边的点，假设右区间存在点 $i$，左区间存在点 $j$，那么 $i$ 对 $j$ 有贡献还需要满足对于右区间的点，不存在 $x_j<x_k<x_i\wedge y_j<y_k<y_i$，去掉一些已经被限制了的条件，那么就是不存在 $x_k<x_i\wedge y_j<y_k$。那么可以对于右区间的点算出满足 $x_k<x_i\wedge y_k<y_i$ 的所有点 $k$ 中 $y_k$ 的最大值，记为 $pre_i$，用树状数组容易维护。

那么限制就可以转化为找 $pre_i<y_j<y_i$ 的点 $j$，这个也可以用树状数组维护，在维护单调栈的时候加点即可。

复杂度 $O(n\log^2n)$。

代码

注意要开 long long。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,ls[N];
long long ans=0;
struct node{
	int x,y;
}a[N];
bool cmpx(node A,node B){
	return A.x<B.x;
}
bool cmpy(node A,node B){
	return A.y<B.y;
}
struct Tree{
	int t[N];
	#define lobit(x) (x&(-x))
	void operator () (int x,int c){
		for(;x<=n;x+=lobit(x)) t[x]+=c;
	}
	int operator [] (int x){
		int ans=0;
		for(;x;x-=lobit(x)) ans+=t[x];
		return ans;
	}
	#undef lobit(x)
}T;
struct M{
	int t[N];
	#define lobit(x) (x&(-x))
	void operator () (int x,int c){
		for(;x<=n;x+=lobit(x)) if(c) t[x]=max(t[x],c); else t[x]=0;
	}
	int operator [] (int x){
		int ans=0;
		for(;x;x-=lobit(x)) ans=max(ans,t[x]);
		return ans;
	}
	#undef lobit(x)
}F;
int stk[N];
void solve(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1;
	solve(l,mid);solve(mid+1,r);
	sort(a+l,a+mid+1,cmpy);sort(a+mid+1,a+r+1,cmpy);
	int i=mid+1,j=l,top=0;
	for(;i<=r;i++){
		for(;j<=mid && a[j].y<a[i].y;j++){
			while(top && a[stk[top]].x<a[j].x) T(a[stk[top--]].y,-1);
			stk[++top]=j;
			T(a[j].y,1);
		}
		ans+=T[a[i].y]-T[F[a[i].x]];
		F(a[i].x,a[i].y);
	}
	while(top) T(a[stk[top--]].y,-1);
	for(int i=mid+1;i<=r;i++) F(a[i].x,0);
//	cout<<l<<" "<<r<<" "<<ans<<"\n";
}
signed mian(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y,ls[i]=a[i].x;
	sort(ls+1,ls+n+1);
	for(int i=1;i<=n;i++) a[i].x=lower_bound(ls+1,ls+n+1,a[i].x)-ls;
	for(int i=1;i<=n;i++) ls[i]=a[i].y;
	sort(ls+1,ls+n+1);
	for(int i=1;i<=n;i++) a[i].y=lower_bound(ls+1,ls+n+1,a[i].y)-ls;
	sort(a+1,a+n+1,cmpx);
	solve(1,n);
	cout<<ans;
	return 0;
}