5683. 统计点对的数目

5683. 统计点对的数目

容斥原理，双指针
这题就仗着 queries的范围小 （1 <= queries.length <= 20）

yxc视频题解

注意求二分的时候我求错了，很值得注意一下。
两个方面：
如果求sorted[l]+sorted[r]<cnt要固定左端点
如果求sorted[l]+sorted[r]>cnt要固定右端点

class Solution {
public:
    vector<int> countPairs(int n, vector<vector<int>>& es, vector<int>& qs) {
        vector<int>d(n+1);
        map<pair<int,int>,int>mp;
        
        for(auto p:es){
            int a=p[0],b=p[1];
            if(a>b)swap(a,b);
            pair<int,int>tp={a,b};
            mp[tp]++;
            d[a]++,d[b]++;
        }
        vector<int>sorted(d.begin()+1,d.end());
        sort(sorted.begin(),sorted.end());
        
        vector<int>res(qs.size());
        for(int i=0;i<qs.size();i++){
            int cur=0;
            int cnt=qs[i];
            for(auto p:mp){
                pair<int,int>point=p.first;
                int freq=p.second;
                int a=point.first,b=point.second;
                if(d[a]+d[b]-freq>cnt)cur++;
                if(d[a]+d[b]>cnt)cur--;
            }

            int l=0,r=n-1;
            // 固定r，如果条件成立就把l~r-1的点都算上，表示左端点是l~r-1，和r匹配
            // 再r--，下面算的是和右端点为r-1的匹配的点个数

            // 如果这个条件是 sorted[l]+sorted[r]<cnt 那就要固定左端点
            // 先算和左端点是l匹配的，右端点为 l+1 ~ r ，再l++
            // 下面就是和左端点是l+1匹配的点
            while(l<r){
                if(sorted[l]+sorted[r]>cnt){
                    cur+=(r-l);
                    r--;
                }
                else l++;
            }
            res[i]=cur;
        }
        
        return res;
    }
};