D - Intersecting Intervals（abc355）

题意：有n个区间，找出俩俩区间相交的个数

分析：

设初始俩俩相交，找出不相交的（不同区间l>r)，减去即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    int n,l[n+10],r[n+10];
    cin>>n;
    ll ans=n*(n-1)/2;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    sort(l+1,l+n+1);
    sort(r+1,r+n+1);
    int k=1;
    for(int i=1;i<=n;i++){
        while(l[i]>r[k]){
            k++;ans--;    
        }
        
    }
    cout<<ans<<endl;
    return 0;
}//然后就超时了

用了一个二分来解决超时问题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
pair<ll,ll>a[N];
int main() {
    ll ans=0,n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){//二分 
        ll lll=i,rr=n;
        while(lll<=rr){
            ll mid=(lll+rr)/2;
            if(a[i].second>=a[mid].first){
                lll=mid+1;
            }else{
                rr=mid-1;
            }
        }
        ans+=lll-i-1;
    }
    cout<<ans;
    return 0;
}