注意到矩形往上是无限的，考虑把点按 $y$ 从大到小考虑
对于枚举到高度为 $h$ 的点，设当前高度大于等于 $h$ 的点的所有点的不同的 $x$ 坐标数量为 $cnt$
那么对于这一层高度 $h$ 我们就有 $cnt(cnt+1)/2$ 种不同的 $l$，$r$ ，使得矩形内点集不同
发现对于某些 $x$ 在这一层相邻两点之间，高度大于 $h$ 的点，这样又重复算了它们的贡献，所有要再扣掉
直接用树状数组维护一下当前区间内不同的 $x$ 的数量即可
因为离散化了判断 $x$ 是否出现过显然直接开一个桶就行....
代码是真的挺简单的，也很容易看懂吧...
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=4e5+7; int n,b[N],m; struct poi { int x,y; poi (int _x=0,int _y=0) { x=_x,y=_y; } inline bool operator < (const poi &tmp) const { return y!=tmp.y ? y>tmp.y : x<tmp.x;//按y从大到小,x从小到大排序 } }p[N]; struct BIT { int t[N]; inline void add(int x) { while(x<=m) t[x]++,x+=x&-x; } inline int ask(int x) { int res=0; while(x) res+=t[x],x-=x&-x; return res; } }T; ll Ans; int tmp[N],tot; bool vis[N]; int main() { n=m=read(); int x,y; for(int i=1;i<=n;i++) { x=read(),y=read(); p[i]=poi(x,y); b[i]=x; } sort(b+1,b+m+1); m=unique(b+1,b+m+1)-b-1; for(int i=1;i<=n;i++) p[i].x=lower_bound(b+1,b+m+1,p[i].x)-b;//离散化 sort(p+1,p+n+1); int cnt=0; for(int i=1;i<=n;i++) { int r=i; tmp[tot=1]=0;/*注意加入0*/ tmp[++tot]=p[i].x; while(p[r+1].y==p[i].y) tmp[++tot]=p[++r].x; tmp[++tot]=m+1;//注意加入m+1 tot=unique(tmp+1,tmp+tot+1)-tmp-1; for(int j=1;j<tot;j++) { int L=tmp[j]+1,R=tmp[j+1]-1; int t=T.ask(R)-T.ask(L-1); Ans-=1ll*t*(t+1)/2;//扣掉会重复算的方案数 } for(int j=i;j<=r;j++) { if(vis[p[j].x]) continue; vis[p[j].x]=1; T.add(p[j].x); cnt++;//不同就加入树状数组 } Ans+=1ll*cnt*(cnt+1)/2; i=r; } printf("%lld\n",Ans); return 0; }