D-Intersecting Intervals
我们思考如何计算不交的线段数量
首先总的线段如果全部相交 那么线段数应为n*(n-1)/2
那么对于每对r[i]<l[i]都为不交的线段
所以我们需要计算不交的线段数 同时删去自己本身
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
void solve(){
int n;cin>>n;
vector<int>l(n),r(n);
for(int i=0;i<n;i++){
cin>>l[i]>>r[i];
}
sort(all(l));sort(all(r));
int ans=n*(n-1)/2;
for(int i=0,j=0;i<n;i++){
while(j<n&&r[j]<l[i])j++;
ans-=j;
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
// cin>>_;
while(_--)solve();
}