abc 355D
作者:
Air1222
,
2024-10-03 17:25:15
,
所有人可见
,
阅读 3
//计数类问题如果不好统计,记得考虑从反面思考问题
//相交区间数=总数-不相交数
//显然不相交数列好统计
//l2>r1|| r2<l1
//注意用stl二分先算地址和差求索引,再数值计算
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e5+10;
int l[N],r[N];
LL sum;
int main()
{
LL n;
cin>>n;
for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
sort(l+1,l+1+n);
sort(r+1,r+1+n);
for(int i=1;i<=n;i++)
{
sum+=(n-(upper_bound(l+1,l+1+n,r[i])-(l+1))+1);
sum+=lower_bound(r+1,r+1+n,l[i])-(r+1)-1;
}
sum/=2;
cout<<n*(n-1)/2-sum;
return 0;
}