CF1859D 题解

shinzAnmono · 2023-08-14 16:07:53 · 题解

CF1859D 题解

读题后发现，对于每一条线段，(b,r] 只能跳回 b，做的是负贡献，[l,b] 可以向前跳，这其实我们把所有 [l,b] 合并起来，然后每次查找 x 所在的线段的右端点，这就变成了一道板题了。

当然，如果 x 不属于任何线段，他最多可以停在自己，所以要特判一下。

#include<iostream>
#include<algorithm>
#include<set>
const int sz=2e5+10;
struct segment{
    int l,r;
    bool operator<(const segment &a)const{
        return l<a.l;
    }
}line[sz];
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin>>t;
    while(t--){
        int n,q;
        std::cin>>n;
        for(int i=1;i<=n;i++){
            int l,r,a,b;
            std::cin>>l>>r>>a>>b;
            line[i]=segment{l,b};
        }
        std::sort(line+1,line+n+1);
        std::set<segment>cur;
        cur.insert(segment{0,0});
        for(int i=1;i<=n;i++){
            int l=line[i].l,r=line[i].r;
            while(i<n&&line[i+1].l>=l&&line[i+1].l<=r)i++,r=std::max(r,line[i].r);
            cur.insert(segment{l,r});
        }
        std::cin>>q;
        for(int i=1,x;i<=q;i++){
            std::cin>>x;
            auto it=--cur.upper_bound(segment{x,x});
            if(x<=it->r)std::cout<<it->r<<" ";
            else std::cout<<x<<" ";
        }
        std::cout<<"\n";
    }
    return 0;
}