ACGO巅峰赛#22+题解

解题思路

1. 定义问题
   设一天划分为 $n$ 个时刻，网友 $i$ 有空的时间区间为 $[l_i, r_i]$。
   Alice 在第 $j$ 天拿起手机的时刻为 $u_j$，放下手机的时刻为 $v_j$，需要连续聊天时长为 $d_j$。

2. 目标
   判断是否存在网友 $i$ ，使得在 $[u_j, v_j]$ 时间段内，能与其连续聊天达到时长 $d_j$。

3. 关键判断
   网友 $i$ 的可聊天区间长度为
   $\text{gap}_i = r_i - l_i + 1$
   若 $\text{gap}_i < d_j$，则该网友不可能满足聊天时长需求。

4. 分两种情况快速判断：

   • 情况1: 网友的起始时间满足
     找最大满足 $l_i \le u_j$ 的网友，若其结束时间满足
     $r_i \ge u_j + d_j - 1$
     则直接输出 "Yes"。

   • 情况2: 需要在区间中找到符合条件的网友
     对所有 $\text{gap}_i \ge d_j$ 的网友，将其起始时刻 $l_i$ 标记。
     查询在区间 $[u_j + 1, v_j - d_j + 1]$ 中是否存在网友的起始时刻。若存在，则输出 "Yes"，否则 "No"。

---

代码解释

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

struct BIT {
    int n;
    vector<int> bit;
    BIT(int n): n(n), bit(n+1,0) {}
    void update(int i, int v) {
        while (i <= n) {
            bit[i] += v;
            i += i & (-i);
        }
    }
    int query(int i) {
        int s = 0;
        while (i > 0) {
            s += bit[i];
            i -= i & (-i);
        }
        return s;
    }
    int query_range(int l, int r) {
        if (l > r) return 0;
        return query(r) - query(l-1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int,int>> netizens(m);
    for (int i = 0; i < m; i++) {
        cin >> netizens[i].first >> netizens[i].second;
    }
    sort(netizens.begin(), netizens.end(), [](auto &a, auto &b) {
        return a.first < b.first;
    });
    vector<int> L(m), R(m);
    for (int i = 0; i < m; i++) {
        L[i] = netizens[i].first;
        R[i] = netizens[i].second;
    }
    vector<int> prefix_max(m);
    prefix_max[0] = R[0];
    for (int i = 1; i < m; i++) {
        prefix_max[i] = max(prefix_max[i-1], R[i]);
    }
    struct Query {
        int u, v, d, idx;
    };
    vector<Query> queries(q);
    for (int i=0; i<q; i++) {
        cin >> queries[i].u >> queries[i].v >> queries[i].d;
        queries[i].idx = i;
    }
    sort(queries.begin(), queries.end(), [](const Query &a, const Query &b) {
        return a.d > b.d;
    });
    vector<pair<int,int>> netizens_by_gap(m);
    for (int i=0; i<m; i++) {
        int gap = R[i] - L[i] + 1;
        netizens_by_gap[i] = {gap, L[i]};
    }
    sort(netizens_by_gap.begin(), netizens_by_gap.end(), [](auto &a, auto &b) {
        return a.first > b.first;
    });
    BIT bit(n);
    vector<string> res(q);
    int p = 0;
    for (auto &qr : queries) {
        int u = qr.u, v = qr.v, d = qr.d, i = qr.idx;

        int p1 = (int)(upper_bound(L.begin(), L.end(), u) - L.begin()) - 1;
        bool part1 = false;
        if (p1 >= 0 && prefix_max[p1] >= u + d - 1) {
            part1 = true;
        }
        if (part1) {
            res[i] = "Yes";
            continue;
        }
        while (p < m && netizens_by_gap[p].first >= d) {
            int pos = netizens_by_gap[p].second;
            bit.update(pos, 1);
            p++;
        }
        int left = u + 1;
        int right = v - d + 1;
        if (left <= right && bit.query_range(left, right) > 0) {
            res[i] = "Yes";
        } else {
            res[i] = "No";
        }
    }
    for (auto &x : res) {
        cout << x << "\n";
    }
    return 0;
}