D. Inconvenient Pairs

观察完样例我们发现发现有且仅有一个共同区间的才是一对
这样我们直接记录x,y 二分出他在哪个区间内
check在共同区间的个数即可
但是还有另一种解法
我们直接对点进行排序 我们将他是这个区间的拿出来 然后就可以直接做了

bool cmp(pair<int,int>a,pair<int,int>b){
    if(a.second<b.second)return 1;
    else return 0;
}
void solve(){
    int n,m,k;cin>>n>>m>>k;
    vector<int>x(n+10),y(m+10);
    map<int,int>stx,sty;
    for(int i=1;i<=n;i++)cin>>x[i],stx[x[i]]++;
    for(int i=1;i<=m;i++)cin>>y[i],sty[y[i]]++;
    vector<pair<int,int>>v(k);
    for(int i=0;i<k;i++)
        cin>>v[i].first>>v[i].second;
    sort(all(v));
    int pos=-1,ans=0;
    for(int i=1;i<=n;i++){
        map<int,int>mpy;
        vector<int>q;
        int sum=0;
        for(int j=pos+1;j<v.size();j++){
            auto [a,b]=v[j];
            if(a<=x[i]){
                pos=j;
                if(!stx[a]){
                    mpy[b]++;
                    sum++;
                    q.push_back(b);
                }
            }else break;
        }
        for(auto j:q)ans+=sum-mpy[j];
    }
    sort(all(v),cmp);
    pos=-1;
    for(int i=1;i<=m;i++){
        map<int,int>mpx;
        vector<int>q;
        int sum=0;
        for(int j=pos+1;j<v.size();j++){
            auto [a,b]=v[j];
            if(b<=y[i]){
                pos=j;
                if(!sty[b]){
                    mpx[a]++;
                    sum++;
                    q.push_back(a);
                }
            }else break;
        }
        for(auto j:q)ans+=sum-mpx[j];
    }
    cout<<ans/2<<endl;
}

原文地址：http://www.cnblogs.com/ycllz/p/16864688.html