题解：AT_abc457_e [ABC457E] Crossing Table Cloth

UnionRE · 2026-05-10 17:07:52 · 题解

记 S 为 m 个线段构成的集合。

考虑两种情况：

[s,t] 和某一个线段

开一个 map<pair<int,int>,int> cnt 记录 [l,r] 线段出现次数。

如果 [s,t] 出现次数 >1 那么肯定是满足的。

否则一定是 [s+1,t] 或 [s,t-1] 的子区间。

如果没有，考虑记录 M_i 表示 \displaystyle\min_{[i,r]\in S}r。对 M_i 做后缀和即可，记为 Mr_i。

满足 Mr_{s+1}\le t 或 Mr_{s}\le t-1 即可。

if(cnt[{s,t}]){
    bool f=0;
    if(cnt[{s,t}]>1)f=1;
    if(minr[s+1]<=t)f=1;
    if(minr[s]<=t-1)f=1;
    if(f==1)cout<<"Yes\n";
    else cout<<"No\n";
    continue;
}

[s,r_1] 和 [l_2,t]。满足 r_1+1\ge l_2

考虑贪心，尽可能最大化 r_1，这样不劣。

那么找到一个满足条件的 l_2 即可。

这个很好维护。dl_x 表示满足 l_i=x 的 [i,r_i] 对，dr_x 表示满足 r_i=x 的 [i,l_i] 对。

auto it=dl[s].upper_bound({0,t});
if(it==dl[s].begin()){
    cout<<"No\n";
    continue;
}
it--;
if(it==dl[s].end()){
    cout<<"No\n";
    continue;
}
int id=(*it).id;
int L1=l[id],R1=r[id];
auto it2=dr[t].upper_bound({0,R1+1});
if(it2==dr[t].begin()){
    cout<<"No\n";
    continue;
}
it2--;
int L2=(*it2).val,R2=r[(*it2).id];
if(it2!=dr[t].end()&&s<=L2&&!(R1<L2-1)){
    if(L1!=L2||R1!=R2)cout<<"Yes\n";
    else cout<<"No\n";
}
else cout<<"No\n";

完整代码

:::info[code]

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int l[maxn],r[maxn];
// struct segl{
//     int l,r;
//     friend bool operator<(segl a,segl b){
//         if(a.l!=b.l)return a.l<b.l;
//         return a.r<b.r;
//     }
// };
// struct segr{
//     int l,r;
//     friend bool operator<(segr a,segr b){
//         if(a.r!=b.r)return a.r<b.r;
//         return a.l<b.l;
//     }
// };
struct info{
    int id,val;
    friend bool operator==(info a,info b){
        return a.val==b.val;
    }
    friend bool operator<(info a,info b){
        return a.val<b.val;
    }
};
set<info> dl[maxn],dr[maxn];
map<pair<int,int>,int> cnt;
int minr[maxn];
signed main() 
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>l[i]>>r[i];
        dl[l[i]].insert({i,r[i]});
        dr[r[i]].insert({i,l[i]});
        cnt[{l[i],r[i]}]++;
    }
    memset(minr,0x7f,sizeof(minr));
    for(int i=n;i>=1;i--){
        minr[i]=minr[i+1];
        for(auto [gunmu,r]:dl[i]){
            minr[i]=min(minr[i],r);
        }
    }
    int q;
    cin>>q;
    while(q--){
        int s,t;
        cin>>s>>t;
        // cout<<s<<' '<<t<<endl;
        // seg1: [s,R1]
        // seg2: [L2,t]
        // R1>=L2-1
        // 贪心，seg1 尽量长
        // 找到 s,R1
        if(cnt[{s,t}]){
            bool f=0;
            if(cnt[{s,t}]>1)f=1;
            if(minr[s+1]<=t)f=1;
            if(minr[s]<=t-1)f=1;
            if(f==1)cout<<"Yes\n";
            else cout<<"No\n";
            continue;
        }
        auto it=dl[s].upper_bound({0,t});
        if(it==dl[s].begin()){
            cout<<"No\n";
            continue;
        }
        it--;
        if(it==dl[s].end()){
            cout<<"No\n";
            continue;
        }
        int id=(*it).id;
        int L1=l[id],R1=r[id];
        auto it2=dr[t].upper_bound({0,R1+1});
        if(it2==dr[t].begin()){
            cout<<"No\n";
            continue;
        }
        it2--;
        int L2=(*it2).val,R2=r[(*it2).id];
        if(it2!=dr[t].end()&&s<=L2&&!(R1<L2-1)){
            if(L1!=L2||R1!=R2)cout<<"Yes\n";
            else cout<<"No\n";
        }
        else cout<<"No\n";
    }
    return 0;
}

:::