题解：AT_abc457_e [ABC457E] Crossing Table Cloth

Shellchen · 2026-05-10 19:36:38 · 题解

分类讨论。对于每个询问 [l,r]：

• 如果有一块恰好是 [l,r] 的布：判断是否有布被它包含，如果有就是 Yes，没有就用下一种情况的方法。
• 如果没有恰好是 [l,r] 的布：找到以 r 结尾，且开头在 l 右边且最大的一块布，判断是否有一块 l 开头，且结尾跨过这块布的布。注意刚好贴着也算。

第一种情况就是一个二维偏序，但是只需要判断是否被偏序，按左端点排序后记录右端点最小值即可。第二种情况对每个点开两个 vector，分别记录左 / 右端点是该值的布的右 / 左端点，查询时二分即可。复杂度 O(q \log m)。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define lowbit(x) ((x)&(-(x)))
const int N=3e5+10,mod=998244353;
vector<int>ll[N],rr[N];
map<pair<int,int>,bool>px;
vector<pair<int,int>>vec;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        vec.push_back({l,r});
        ll[l].push_back(r);
        rr[r].push_back(l);
    }
    sort(vec.begin(),vec.end(),greater<pair<int,int>>());
    int mn=1e18;
    for(auto v:vec)
    {
        if(v.se>=mn) px[v]=1;
        mn=min(mn,v.se);
    }
    for(int i=1;i<=n;i++)
    {
        sort(ll[i].begin(),ll[i].end());
        sort(rr[i].begin(),rr[i].end());
    }
    int q;
    cin>>q;
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        if(!rr[r].size()||!ll[l].size())
        {
            cout<<"No\n";
            continue;
        }
        auto itl=lower_bound(rr[r].begin(),rr[r].end(),l);
        if(itl==rr[r].end())
        {
            cout<<"No\n";
            continue;
        }
        int tl=*itl;
        if(tl==l&&px[{l,r}])
        {
            cout<<"Yes\n";
            continue;
        }
        int fl=lower_bound(ll[l].begin(),ll[l].end(),tl-1)-ll[l].begin(),fr=lower_bound(ll[l].begin(),ll[l].end(),r+1)-ll[l].begin()-1;
        if(fl>fr||(fl==fr&&tl==l&&ll[l][fl]==r)) cout<<"No\n";
        else cout<<"Yes\n";
    }
    return 0; 
}

:::