C++ 解法, 执行用时: 153ms, 内存消耗: 14264K, 提交时间: 2021-07-20 13:58:29

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
struct AA{
	int x,y;
}a[100005];
int b[200005],cnt;
ll sum[800005],bj[800005],g[800005],ans;

int cmp(AA u,AA v){
	if(u.x==v.x) return u.y<v.y;
	return u.x<v.x;
}

void lazy(int u,int l,int r){
	sum[u]+=bj[u]*g[u];
	if(l==r){
		bj[u]=0;return;
	}
	bj[2*u]+=bj[u];
	bj[2*u+1]+=bj[u];
	bj[u]=0;
}

void updata(int u,int l,int r,int c){
	if(bj[u]) lazy(u,l,r);
	if(l>c||r<c) return;
	if(l==r){
		g[u]++;return;
	}
	int mid=(l+r)/2;
	updata(2*u,l,mid,c);
	updata(2*u+1,mid+1,r,c);
	g[u]=g[2*u]+g[2*u+1];
	sum[u]=sum[2*u]+sum[2*u+1];
}

void add(int u,int l,int r,int L,int R){
	if(bj[u]) lazy(u,l,r);
	if(l>R||r<L) return;
	if(L<=l&&R>=r){
		bj[u]++,lazy(u,l,r);
		return;
	}
	int mid=(l+r)/2;
	add(2*u,l,mid,L,R);
	add(2*u+1,mid+1,r,L,R);
	sum[u]=sum[2*u]+sum[2*u+1];
}

ll query(int u,int l,int r,int L,int R){
	if(bj[u]) lazy(u,l,r);
	if(l>R||r<L) return 0;
	if(L<=l&&R>=r) return sum[u];
	ll ans=0;
	int mid=(l+r)/2;
	ans=query(2*u,l,mid,L,R)+query(2*u+1,mid+1,r,L,R);
	return ans;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d",&a[i].x,&a[i].y);
		b[++cnt]=a[i].x,b[++cnt]=a[i].y;
	}
	sort(b+1,b+cnt+1);
	for(int i=1;i<=n;i++){
		a[i].x=lower_bound(b+1,b+cnt+1,a[i].x)-b;
		a[i].y=lower_bound(b+1,b+cnt+1,a[i].y)-b;
	}
	sort(a+1,a+n+1,cmp);
	int L=1;
	for(int i=1;i<=n;i++){
		if(a[i].x!=a[L].x){
			for(int j=L;j<i;j++) add(1,1,cnt,a[j].y+1,cnt);
			for(int j=L;j<i;j++) updata(1,1,cnt,a[j].y);
			L=i;
		}
		ans+=query(1,1,cnt,1,a[i].y-1);
	}
	printf("%lld\n",ans);
	
	return 0;
}