按x轴进行分治，将[l,r]分成[l,mid]和[mid+1,r]，左下角点x值在[l,mid]中，右上角点x值在[mid+1,r],然后将[l,r]中的所有点按y轴排序，按顺序扫描，若扫描到左下角点，用一个单调栈维护，若扫描到右上角点，用另一个单调栈维护的同时，去维护左下角的单调栈中二分出答案，复杂度O(nlognlogn),程序跑的有点慢
代码
#include<cstdio>
#include<algorithm>
#include<set>
#define N 500010
using namespace std;
int n,i;
long long ans;
int top1,top2,stack1[N],stack2[N];
struct g{
int x,y;
}a[N];
bool cmp(g a,g b)
{
return a.x<b.x;
}
bool cmp1(g a,g b)
{
return a.y<b.y;
}
int ef(int x)
{
int l=,r=top1,m;
while (l<=r)
{
m=(l+r)>>;
if (x>a[stack1[m]].y) l=m+;else r=m-;
}
return r;
}
void solve(int L,int R,int l,int r)
{
int p,q;
if (L>=R) return;
if (l>=r) return;
int m=(L+R)>>;
int cnt=l,i;
int t;
for (i=l;i<=r;i++)
if (a[i].x<=m)
{
t=a[i].x;a[i].x=a[cnt].x;a[cnt].x=t;
t=a[i].y;a[i].y=a[cnt].y;a[cnt].y=t;
cnt++;
} if ((l<cnt)&&(cnt<=r))
{
sort(a+l,a+cnt,cmp1);
sort(a+cnt,a++r,cmp1); top1=;top2=;
p=l;q=cnt;
while ((p<cnt)||(q<=r))
{
if ((p==cnt)||((q<=r)&&(a[q].y<a[p].y)))
{
while ((top2)&&(a[q].x<a[stack2[top2]].x)) top2--;
ans+=ef(a[q].y)-ef(a[stack2[top2]].y);
top2++;stack2[top2]=q;q++;
}
else
{
while ((top1)&&(a[p].x>a[stack1[top1]].x)) top1--;
top1++;stack1[top1]=p;p++;
}
} }
/*
printf("%d %d\n",L,R);
printf("A:\n");
for (i=l;i<cnt;i++)
printf("%d %d\n",a[i].x,a[i].y);
printf("B:\n");
for (i=cnt;i<=r;i++)
printf("%d %d\n",a[i].x,a[i].y);
*/
solve(L,m,l,cnt-);
solve(m+,R,cnt,r);
}
int main()
{
scanf("%d",&n);
for (i=;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].y++;
}
sort(a+,a++n,cmp);
for (i=;i<=n;i++)
a[i].x=i;
solve(,n,,n);
printf("%lld\n",ans);
}