聊天室
题目大意
一天一共有 nnn 个时刻 ,其中有 mmm 个线段,每一个线段从 lil_ili 开始, 到 rir_iri 结束。现在有 qqq 次询问,每次询问有一个 lil_ili rir_iri did_idi ,问已知区间有没有能和现在的区间相交为 did_idi 。
题解思路
题目分析
这个问题描述了一个场景:Alice 有 m 位网友,每位网友每天在固定的时间段 [li,ri][l_i, r_i][li ,ri ] 内可以聊天。接下来有 q 天,每天 Alice 会在 [ui,vi][u_i, v_i][ui ,vi ] 时间段内寻找网友聊天,如果能找到一位网友可以持续聊天 d_i 时长,就能放松。我们需要判断每一天 Alice 是否能成功放松。
解题思路
1. 问题转化:我们需要判断是否存在一位网友,其在线时间段 [li,ri][l_i, r_i][li ,ri ] 与 Alice 的查询时间段 [ui,vi][u_i, v_i][ui ,vi ] 的交集长度 ≥di\ge d_i≥di 。
2. 关键观察:
* 交集长度 = min(ri,vi)−max(li,ui)+1≥dimin(r_i, v_i) - max(l_i, u_i) + 1 \ge d_imin(ri ,vi )−max(li ,ui )+1≥di
* 可以转化为三种情况:
* a) 网友的右端点足够大:ri≥ui+di−1r_i \ge u_i + d_i - 1ri ≥ui +di −1
* b) 网友的左端点足够小:li≥vi−di+1l_i \ge v_i - d_i + 1li ≥vi −di +1
* c) 网友的在线时长足够长:ri−li+1≥dir_i - l_i + 1 \ge d_iri −li +1≥di
3. 数据结构选择:
* 使用线段树(Segment Tree)来高效查询区间信息
* 分别处理上述三种情况,用三个线段树来维护
参考代码