题解：AT_abc457_e [ABC457E] Crossing Table Cloth

· · 题解

对于成功的情况进行分讨。

  1. 使用两张布拼起来。
  2. 一张布恰好完全覆盖，再随意选一张被完全包含在 [S, T] 内的布。

对于第一种情况，选的布里面肯定有一张的左端点在 S，另一张右端点在 T。
分别记录下以 x 为左右端点时，另一端点的位置。贪心的选择能用的最长的布。
对于第二种情况，我们可以将询问离线下来，从大到小枚举 S_i，并将 L_j \ge _i 的 R_j 用树状数组记下来。查询 R \le T_i 的数量是否 \ge 2。
注意这是一个格子覆盖问题而非线段覆盖问题，存在 R_i + 1 = L_j 的情况。 ::::success[Code]

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;

const int MAXN = 2e5 + 9;

int n, m, q;
string ans[MAXN];
vector<pii> vl[MAXN], vr[MAXN];
pair<pii, int> nq[MAXN];
struct FWT {
    int t[MAXN];
    int lowbit(int x) {
        return x & (-x);
    }
    void add(int x, int v) {
        while(x <= n) {
            t[x] += v;
            x += lowbit(x);
        }
    }
    int query(int x) {
        int res = 0;
        while(x) {
            res += t[x];
            x -= lowbit(x);
        }
        return res;
    }
} fwt;
void solve() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        vl[r].push_back({l, i});
        vr[l].push_back({r, i});
    }
    cin >> q;
    for(int i = 1; i <= q; i++) {
        cin >> nq[i].fi.fi >> nq[i].fi.se;
        nq[i].se = i;
    }
    for(int i = 1; i <= n; i++) sort(vr[i].begin(), vr[i].end()), sort(vl[i].begin(), vl[i].end());
    sort(nq + 1, nq + q + 1);
    for(int i = q, lst = n + 1; i; i--) {
        int ql = nq[i].fi.fi, qr = nq[i].fi.se, id = nq[i].se;
        while(lst > ql) {
            lst--;
            for(auto it : vr[lst]) fwt.add(it.fi, 1);
        }
        bool flag1 = 0, flag2 = 0;
        auto itl = upper_bound(vr[ql].begin(), vr[ql].end(), (pii){qr, m + 1});
        if(itl != vr[ql].begin()) {
            itl--;
            flag1 = 1;
        }
        auto itr = lower_bound(vl[qr].begin(), vl[qr].end(), (pii){ql, 0});
        if(itr != vl[qr].end()) flag2 = 1;
        if(!flag1 || !flag2) ans[id] = "No";
        else if(itl -> se != itr -> se) {
            if(itl -> fi + 1 >= itr -> fi) ans[id] = "Yes";
            else ans[id] = "No";
        }
        else {
            if(fwt.query(qr) >= 2) ans[id] = "Yes";
            else ans[id] = "No";
        }
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return;
}

int main() {
    solve();
    return 0;
}

::::