Codeforces Round 892 (Div. 2) D. Andrey and Escape from Capygrad-Toy模板网

这篇具有很好参考价值的文章主要介绍了Codeforces Round 892 (Div. 2) D. Andrey and Escape from Capygrad。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Codeforces Round 892 (Div. 2) D. Andrey and Escape from Capygrad,cf补题,算法,数据结构

题意：给定区间[l,r],[a,b],[a,b]包含于[l,r],可以从任意[l,r]的区间传送至[a,b],给定指定的点求能传送的最远距离。

思路：可以将区间简化为[l,b]，因为l可以看作是最左边，b可以看作是能到达的最右端点，然后进行区间合并即可。

对于查询，我们使用二分去找 x所在的区间，方法：对于每一个区间，寻找第一个小于等于x的左端即可，这样就保证了x一定会处于该区间内。文章来源地址https://www.toymoban.com/news/detail-649628.html

#include<bits/stdc++.h>

using namespace std;
const int N=2e5+5;
typedef long long ll;
typedef pair<ll,ll > pll;
typedef array<int,3> p3;
int mod=998244353;
const int maxv=4e6+5;


void solve()
{	
    int n;
    cin>>n;
    vector<pll> se(n);
    for(int i=0;i<n;i++){
        int l,r,a,b;
        cin>>l>>r>>a>>b;
        se[i]={l,b};
    }
    sort(se.begin(),se.end());
    vector<pll> sm;
    for(int i=0;i<n;i++){
        auto [l,r]=se[i];
        if(sm.empty()){
            sm.push_back({l,r});
        }
        else{
            auto [nl,nr]=sm.back();
            if(nr>=l){
                sm.back().second=max(sm.back().second,r);
            }
            else{
                sm.push_back({l,r});
            }
        }
    }
    int q;
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        int t=lower_bound(sm.begin(),sm.end(),(pll){x+1,0})-sm.begin()-1;
        ll ans=x;
        if(t>=0){
            ans=max(ans,sm[t].second);
        }
        cout<<ans<<" ";
    }
    cout<<endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int t;
	t=1;
	cin>>t;
    while(t--){
        solve();
    }
	system("pause");
	return 0;
}

到了这里，关于Codeforces Round 892 (Div. 2) D. Andrey and Escape from Capygrad的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！