CF1859D 题解
shinzanmono
2023-08-14 16:07:53
# CF1859D 题解
读题后发现，对于每一条线段，$(b,r]$ 只能跳回 $b$，做的是负贡献，$[l,b]$ 可以向前跳，这其实我们把所有 $[l,b]$ 合并起来，然后每次查找 $x$ 所在的线段的右端点，这就变成了一道板题了。
当然，如果 $x$ 不属于任何线段，他最多可以停在自己，所以要特判一下。
```cpp
#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;
}
```