D. Searchlights 思维 偏序

 Problem - D - Codeforces

 题意：分别给你一个n个pair<a,b>和m个pair<c,d>，问最少操作数，可以使得对于所有的<a,b>，对于任意的<c,d>，都有(a>c)或(b>d)。两个条件满足其一即可。

　　操作的定义是，在一次操作中，你可以选a或b，然后对于所有的你选定的，都加1

解法：对于每一个m，我们遍历n来求要满足上述条件的pair，经过m*n次操作，我们得到了一个数组，然后对其以sort，并且删去b元素小于等于最后一个元素不相交的，并不断更新这个值。看图更好理解

我们要删掉图中蓝色和紫的，而保留这个绿色的，因为我们要满足这个绿色时候，一定能满足蓝色和紫色的需求。

然后我们的到了类似于上图这样的pair数组，数字上小下大，我们发现当我们取紫色元素的b时，大家都能被覆盖，当我们取橙色的a时同理。我们发现当我们取一个a后，小于其a的就都不用考虑了，而且b的大小顺序是相反的，所以我们再取一个b，能覆盖剩下的元素就ok了，那么根据贪心，我们肯定取最小的b，而且如果a时按照升序排列的，则b一定按照降序排列，因为要相交。所以我们就取下一个b元素即可。扫一遍取min然后特判两个端点即可

void solve(){
    int n,m;cin>>n>>m;
    vector<pii>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i].fi>>a[i].se;
    vector<pii>b;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        for(int i=1;i<=n;i++){
            if(x<a[i].fi||y<a[i].se)continue;
            b.push_back({x-a[i].fi+1ll,y-a[i].se+1ll});
        }
    }
    if(b.size()==0){
        cout<<0<<"\n";return ;
    }
    sort(b.begin(),b.end());
    //for(auto &i:b)cout<<i.fi<<" "<<i.se<<"\n";
    vector<pii>c;
    c.push_back(*(b.end()-1));
    int lt=(b.end()-1)->se;
    for(int i=(int)b.size()-2;i>=0;i--)if(b[i].se>lt){lt=b[i].se;c.push_back(b[i]);}
    n=c.size();
    //for(auto i:c)cout<<i.fi<<" "<<i.se<<"\n";
    int ans=min(c[0].fi,c[n-1].se);
    for(int i=1;i<n;i++){
        ans=min(ans,c[i].fi+c[i-1].se);
    }
    cout<<ans<<"\n";
}