题解：AT_abc457_e [ABC457E] Crossing Table Cloth

_zyx2012 · 2026-05-10 09:50:27 · 题解

看到很多人都在用 set、ST 表、BIT 之类的 Data-Structure 做。

这里讲一个不需要 DS 的做法。

首先，对于每个询问 [s_q,t_q]，分两种情况讨论：

• 存在 i 满足 [l_i,r_i]=[s_q,t_q]：

  现在要看是否存在 j \neq i 满足 s_q \leq l_j \leq r_j \leq t_q。

  很明显，$r_j$ 越小，条件越容易满足，那我们去找 $\min\limits_{l_j \geq s_q}\{r_j\}$，如果这个值本身就已经小于 $t_q$ 了，那答案就是 `Yes`，而这个 $\min\limits_{l_j \geq s_q}\{r_j\}$ 只需要记 $msr_i = \min\limits_{l_j \geq i}\{r_j\}$，这个可以在预处理的时候从后往前扫一遍算出来，查询的时候去 $msr$ 里边查表即可。 求 $msr$ 的代码： ```cpp for (;m--;){ int L,R; cin >> L >> R; msr[L] = min(msr[L],R); } for (int i = n;i;i--) msr[i] = min(msr[i],msr[i + 1]); ``` $\min\limits_{l_j \geq s_q}\{r_j\}=t_q$ 为什么不行？因为这个时候，你无法保证 $j \neq i$。 那么，此时肯定不存在任何一个 $j$ 满足 $s_q \lt l_j \leq r_j \leq t_q$。 现在就只能在 $l_j=s_q$ 的 $j$ 中找 $r_j$ 最小的，$r_j=t_q$ 的 $k$ 中找 $l_k$ 最大的，注意不要找到 $i$ 自己，如果 $r_j \leq t_q$ 或者 $s_q \leq l_k$，那答案就是 `Yes`，否则就是 `No`。

• 不存在 i 满足 [l_i,r_i]=[s_q,t_q]：

  这一部分比较简单，找出满足 l_j=s_q,r_j \leq t_q 中找出 r_j 最大的 j，满足 r_k=t_q,l_k \geq s_q 中找出 l_k 最小的 k，如果 r_j+1 \leq l_k，就说明它俩可以覆盖，答案为 Yes，否则为 No。

Code:

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using i128 = __int128;
using u128 = unsigned __int128;

mt19937_64 mrand((u64)random_device{}() << 32 ^ random_device{}() ^
    chrono::high_resolution_clock::now().time_since_epoch().count());
template<class T = i64,class T2>T rnd(T l,T2 r){
return uniform_int_distribution<T>(l,r)(mrand);}

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int n,m;
    cin >> n >> m;

    vector<vector<int>> l(n + 1),r(n + 1);
    vector<int> msr(n + 2,1e9);

    for (;m--;){
        int L,R;
        cin >> L >> R;

        msr[L] = min(msr[L],R);

        l[L].push_back(R);
        r[R].push_back(L);
    }

    for (int i = n;i;i--){
        msr[i] = min(msr[i],msr[i + 1]);
        sort(l[i].begin(),l[i].end());
        sort(r[i].begin(),r[i].end());
    }

    int q;
    cin >> q;

    for (;q--;){
        int L,R;
        cin >> L >> R;

        int x = upper_bound(l[L].begin(),l[L].end(),R) - l[L].begin();
        int y = lower_bound(r[R].begin(),r[R].end(),L) - r[R].begin();

        if (x&&l[L][x - 1] == R){
            if (x > 1||y + 1 < (int)r[R].size()||msr[L] < R)
                cout << "Yes\n";
            else
                cout << "No\n";
            continue;
        }

        cout << (x&&y != (int)r[R].size()&&r[R][y] <= l[L][x - 1] + 1?"Yes":"No") << '\n';
    }
}

都看到这了还不点个赞，

那还是人吗？