总结

一种经典的题型，诸如区间合并，区间选择等

区间合并

vector<PII> q;
for(int i=1;i<=n;i++){
    cin>>a[i]>>b[i];
    mx=max({mx,a[i],b[i]});
    if(a[i]>=b[i]){
        mn=min(mn,b[i]);
        q.pb({b[i],a[i]});
    }
}
sort(all(q));
vector<PII> s;
for(auto [l,r] : q){
    if(!s.empty()&&l<=s.back()[1]){
        s.back()[1]=max(s.back()[1],r);
    }else{
        s.push_back({l,r});
    }
}

智乃的k线段区间

地址

先预处理出所有“包含K条线段”的最小区间

利用 map 对 key 的排序使右端点有序，再分别把 l 放入 multiset 使左端点有序

保证 multiset 的大小为 k，此时的左右端点即为最小区间

void solve()
{
    int n,m,k;
    cin>>n>>m>>k;
    map<int,vector<int>> mp;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        mp[r].push_back(l);
    }
    multiset<int> s;
    ll ans=0;
    int left=1;
    for(auto [r,v] : mp){
        for(auto l:v){
            s.insert(l);
        }
        while(s.size()>k){
            s.erase(s.begin());
        }
        if(s.size()==k){
            int tp=*s.begin();
            ans+=(tp-left+1)*(m-r+1);
            left=tp+1;
        }
    }
    cout<<ans<<'\n';
}