题解：
判断每一次加进来的时候有几个被破坏，几个添加
然后单调栈维护
代码：
#include<bits/stdc++.h> using namespace std; const int N=5005; int n,j,k,ans=0,now,oo=10000000; struct note{int x,y,id;}a[N],b[N]; bool cmp(const note i,const note j){return i.x<j.x;} struct stack { note e[N]; int l,h,t; void pre(int z){l=0;h=t=0;e[0].x=now;e[0].y=oo*z;} void add(note a,bool z){if ((a.y<e[l].y)^z)e[++l]=a;} void Xwork(int x,bool z){while (h<=l&&((e[h].x<x)^z))h++;h?h--:0;} void Ywork(int y,bool z){while (t<=l&&((e[t].y<y)^z))t++;} }c1,c2,c3,c4; int main() { scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y),a[i].id=i; memcpy(b,a,sizeof(b)); std::sort(b+1,b+n+1,cmp); for (int i=1;i<=n;i++) { now=a[i].x;c1.pre(1),c2.pre(1);c3.pre(-1),c4.pre(-1); for (k=1;k<=n&&b[k].x<a[i].x;k++); for (j=k-1;j;j--) if (b[j].id<i) if (b[j].y>a[i].y) c2.add(b[j],0); else c3.add(b[j],1); for (j=k;j<=n;j++) if (b[j].id<i) if (b[j].y>a[i].y) c1.add(b[j],0); else c4.add(b[j],1); ans+=c1.l+c2.l+c3.l+c4.l; for (int j=1;j<=c1.l;j++) { int x=c1.e[j].x,y=c1.e[j].y,xx,yy; if (!c3.l) continue; c2.Ywork(y,1);xx=c2.e[c2.t].x; if (c2.t>c2.l) xx=-oo;c3.Xwork(xx,1); c4.Xwork(x,0);yy=c4.e[c4.h].y;c3.Ywork(yy,0); c3.h>c3.l?c3.h--:0;c3.t?0:c3.t++; ans-=max(c3.h-c3.t+1,0); } c2.h=c2.t=c3.h=c3.t=c4.h=c4.t=1; for (int j=1;j<=c4.l;j++) { int x=c4.e[j].x,y=c4.e[j].y,xx,yy; if (!c2.l) continue; c3.Ywork(y,0);xx=c3.e[c3.t].x; if (c3.t>c3.l) xx=-oo;c2.Xwork(xx,1); c1.Xwork(x,0);yy=c1.e[c1.h].y;c2.Ywork(yy,1); c2.h>c2.l?c2.h--:0;c2.t?0:c2.t++;ans-=max(c2.h-c2.t+1,0); } printf("%d ",ans); } return 0; }