扫描线，差分

CF995 E

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
const int N=2e5+10;
#define int long long
int a[N],b[N];
signed main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        vector<pii> st;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            st.push_back({a[i]+1,1});
            st.push_back({a[i]+1,0});
            st.push_back({a[i],0});
        }
        for(int i=1;i<=n;i++){
            cin>>b[i];
            st.push_back({b[i]+1,-1});
            st.push_back({b[i],0});
            st.push_back({b[i]+1,0});
        }
        int cnt=n;
        sort(st.begin(),st.end(),[](const pii x,const pii y){
            if(x.first==y.first) return x.second>y.second;
            return x.first<y.first;
        });
        int sum=0;
        int ans=0;
        for(int i=0;i<st.size();){
            int x=st[i].first,y=st[i].second;
            int ei=i;
            while(ei<st.size()&&st[ei].first==st[i].first){
                sum+=st[ei].second;
                if(st[ei].second==-1) cnt--;
                ei++;
            }
            if(sum<=k) ans=max(ans,cnt*(x));
            i=ei;
        }
        cout<<ans<<endl;
    }
    return 0;
}

牛客周赛85 E

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
struct node{
    int l,r,id;
    bool operator<(const node x)const {
        return l<x.l;
    }
};
int main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int n;
    cin>>n;
    vector<node> a(n+1);
    vector<pii> v;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        a[i].l=l,a[i].r=r,a[i].id=i;
        v.push_back({l,1});
        v.push_back({r+1,-1});
    }
    sort(v.begin(),v.end());
    int sum=0;
    for(auto& [x,y]:v){
        sum+=y;
        if(sum>2){
            cout<<-1<<endl;
            return 0;
        }
    }
    sort(a.begin()+1,a.end());
    int mx=0;
    vector<int> ans;
    int color=0;
    for(int i=1;i<=n;i++){
        int now=0;
        now=color^1;
        if(now==1) ans.push_back(a[i].id);
        if(a[i].r>mx){
            mx=a[i].r;
            color=now;
        }
    }
    cout<<ans.size()<<endl;
    for(auto x:ans){
        cout<<x<<" ";
    }
    return 0;
}