AT_abc457_e 解题报告
jinhungqian
·
·
题解
AT_abc457_e 解题报告
作者提示：相接定义为 x \ge y，或两者刚好相邻。
形式化题面
给你 n 个格子和 m 块布，第 i 块布覆盖 [l_i,r_i] 这个区间。
回答 q 个问题，第 i 个问题给出 s_i 和 t_i，让你求出能否用两块布恰好覆盖 [s_i,t_i] 这个区间，而不覆盖其他任何格子。
分析
这两块布的覆盖可以分为两种情况：
-
一个覆盖 [s,x]，另一个覆盖 [y,t]，还需满足 x 与 t 相接（不是单纯的符号关系）。我就是因为这个找半天没找出来。
-
有一个区间直接覆盖 [s,t]，直接找出另一个区间被 [s,t] 包含即可。
判断
对于第一种情况，我们要找出 x 在小于等于 t 的情况下的最大值和 y 在大于等于 s 下的最小值，若被查到的都是一个区间，就说明该区间就是 [s,t]。可以直接判断有没有另一个区间被 [s,t] 包含，不然就判断是否相接。
算法分析
找在这些约束条件下的最大值可以直接用二分写。
至于包含，只要枚举开始编号即可。
算法复杂度
~~很丑。~~
## 代码
``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define endl "\n"
const int N=2e5+5;
int n,m,q;
struct ridx{
int to,idx;
};
vector<ridx> ltor[N],rtol[N];
bool cmp1(ridx x,ridx y){
return x.to<y.to;
}
bool cmp2(ridx x,ridx y){
return x.to>y.to;
}
bool bh(int s,int t){
int cnt=0;
for(int i=s;i<=t;i++){
if(ltor[i].empty()) continue;
int ans=-1;
int l,r;
l=0,r=ltor[i].size()-1;
while(l<=r){
int mid=(l+r)>>1;
if(ltor[i][mid].to<=t){
ans=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
ans++;
cnt+=ans;
if(cnt>1){
return true;
}
}
return false;
}
bool query(int s,int t){
if(ltor[s].empty()||rtol[t].empty()){
return false;
}
int totj=-1,totans,totid;
int l,r;
l=0,r=ltor[s].size()-1;
while(l<=r){
int mid=(l+r)>>1;
if(ltor[s][mid].to<=t){
totj=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
if(totj==-1) return false;
totans=ltor[s][totj].to;
totid=ltor[s][totj].idx;
int tosj=-1,tosans,tosid;
l=0,r=rtol[t].size()-1;
while(l<=r){
int mid=(l+r)>>1;
if(rtol[t][mid].to>=s){
tosj=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
if(tosj==-1) return false;
tosans=rtol[t][tosj].to;
tosid=rtol[t][tosj].idx;
if(totid==tosid){
return bh(s,t);
}
return totans>=tosans-1;
}
int main(){
fastio;
cin>>n>>m;
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
ltor[l].push_back({r,i});
rtol[r].push_back({l,i});
}
for(int i=1;i<=n;i++){
if(!ltor[i].empty()){
sort(ltor[i].begin(),ltor[i].end(),cmp1);
}
if(!rtol[i].empty()){
sort(rtol[i].begin(),rtol[i].end(),cmp2);
}
}
cin>>q;
while(q--){
int s,t;
cin>>s>>t;
if(query(s,t)){
cout<<"Yes\n";
}
else{
cout<<"No\n";
}
}
return 0;
}
```