聊天室

题目大意

一天一共有 $n$ 个时刻 ，其中有 $m$ 个线段，每一个线段从 $l_i$ 开始， 到 $r_i$ 结束。现在有 $q$ 次询问，每次询问有一个 $l_i$ $r_i$ $d_i$,问已知区间有没有能和现在的区间相交为 $d_i$。

题解思路

题目分析

这个问题描述了一个场景：Alice 有 m 位网友，每位网友每天在固定的时间段 $[l_i, r_i]$ 内可以聊天。接下来有 q 天，每天 Alice 会在 $[u_i, v_i]$ 时间段内寻找网友聊天，如果能找到一位网友可以持续聊天 d_i 时长，就能放松。我们需要判断每一天 Alice 是否能成功放松。

解题思路

1. 问题转化：我们需要判断是否存在一位网友，其在线时间段 $[l_i, r_i]$ 与 Alice 的查询时间段 $[u_i, v_i]$ 的交集长度 $\ge d_i$。

2. 关键观察：

   • 交集长度 = $min(r_i, v_i) - max(l_i, u_i) + 1 \ge d_i$
   • 可以转化为三种情况：

     • a) 网友的右端点足够大：$r_i \ge u_i + d_i - 1$

     • b) 网友的左端点足够小：$l_i \ge v_i - d_i + 1$

     • c) 网友的在线时长足够长：$r_i - l_i + 1 \ge d_i$

3. 数据结构选择：

   • 使用线段树（Segment Tree）来高效查询区间信息
   • 分别处理上述三种情况，用三个线段树来维护

参考代码

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

class STG {
public:
    int n;
    vector<int> arr;

    STG(int n) : n(n), arr(4 * n) {
    }

    int query(int q, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return arr[q];
        }
        if (l > R || r < L || l > r) return 0;
        int mid = (l + r) / 2;
        return max(query(q << 1, l, mid, L, R), query(q << 1 | 1, mid + 1, r, L, R));
    }

    void push_up(int q) {
        arr[q] = max(arr[q << 1], arr[q << 1 | 1]);
    }

    void modify(int q, int l, int r, int pos, int x) {
        if (l == r) {
            arr[q] = max(arr[q], x);
            return;
        }
        int mid = (l + r) / 2;
        if (mid >= pos) {
            modify(q << 1, l, mid, pos, x);
        } else modify(q << 1 | 1, mid + 1, r, pos, x);
        push_up(q);
    }
};


int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int> > arr(m + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        arr[i] = {u, v};
    }

    vector<int> ans(q + 1);
    vector<tuple<int, int, int> > ask(q + 1);
    for (int i = 1; i <= q; i++) {
        int l, r, d;
        cin >> l >> r >> d;
        ask[i] = {l, r, d};
    } {
        STG s1(n + 1);
        vector<vector<int> > r1(n + 1);
        vector<vector<pair<int, int> > > ar1(n + 1);
        for (int i = 1; i <= m; i++) {
            r1[arr[i].first].emplace_back(arr[i].second);
        }
        for (int i = 1; i <= q; i++) {
            auto [l, r ,d] = ask[i];
            ar1[l].emplace_back(l + d - 1, i);
        }
        for (int i = 1; i <= n; i++) {
            for (auto r: r1[i]) {
                s1.modify(1, 1, n, r, 1);
            }
            for (auto [r, id]: ar1[i]) {
                int t = s1.query(1, 1, n, r, n);
                ans[id] |= t;
            }
        }
    } {
        STG s2(n + 1);
        vector<vector<int> > l1(n + 1);
        vector<vector<pair<int, int> > > al1(n + 1);
        for (int i = 1; i <= m; i++) {
            l1[arr[i].second].emplace_back(arr[i].first);
        }
        for (int i = 1; i <= q; i++) {
            auto [l, r ,d] = ask[i];
            al1[r].emplace_back(r - d + 1, i);
        }
        for (int i = n; i; i--) {
            for (auto l: l1[i]) {
                s2.modify(1, 1, n, l, 1);
            }
            for (auto [l, id]: al1[i]) {
                int t = s2.query(1, 1, n, 1, l);
                ans[id] |= t;
            }
        }
    } {
        STG s3(n + 1);
        vector<vector<int> > lr1(n + 1);
        vector<vector<pair<int, int> > > alr1(n + 1);
        for (int i = 1; i <= m; i++) {
            auto [l , r] = arr[i];
            lr1[r - l + 1].emplace_back(l);
        }
        for (int i = 1; i <= q; i++) {
            auto [l, r ,d] = ask[i];
            alr1[d].emplace_back(r - d + 1, i);
        }
        for (int i = n; i; i--) {
            for (auto l: lr1[i]) {
                // cerr << "modify" << " " << l << " " << 1 << endl;
                s3.modify(1, 1, n, l, 1);
            }
            for (auto [_, id]: alr1[i]) {
                auto [l, r ,d] = ask[id];
                int t = s3.query(1, 1, n, l, r-d +1 );
                ans[id] |= t;
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        if (ans[i]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}