简单题解：礼物交换可行性判断

核心结论：利用 Hall 定理转化问题，通过预处理和前缀和查询，快速判断每个区间是否满足“完美匹配”条件，从而确定组合是否可行。

一、核心思路（通俗版）

1. 问题本质：学生和礼物的匹配是“二分图完美匹配”——每个学生要收到别人的礼物（无自环），且礼物价值≥自己的要求（B_i）。
2. Hall 定理简化：对于区间 [L, R]，只要满足“任意 k 个学生，至少有 k 个符合要求的礼物（来自区间内其他人）”，就存在可行的交换方式。
3. 关键转化：把每个学生 i 映射到一个“有效范围”，再通过预处理和前缀和，快速检查区间是否满足 Hall 条件，避免逐个验证。

二、步骤拆解（分两步走）

1. 预处理阶段（O(N log N)）

• 给每个学生 i 算两个值：
  • Pre[i]：学生 i 能“接收”的礼物对应的最小学生编号（简单说，就是哪些人能给 i 送礼物）。
  • Nex[i]：学生 i 能“接收”的礼物对应的最大学生编号。
• 这一步用线段树快速查询和更新，核心是找到每个 i 满足 A_j ≥ B_i（j 是送礼物的人）的 j 的范围。

2. 查询处理阶段（O(Q log N)）

• 把所有查询 [L, R] 按 R 分组（离线处理，避免重复计算）。
• 用树状数组（前缀和工具）维护：对于当前 R，检查所有以 R 为右端点的查询 [L, R]，是否满足 Hall 条件。
• 若查询结果为 0，说明满足条件，输出 Yes；否则输出 No。

三、代码核心逻辑（通俗解释）

• 线段树：用来快速找每个学生的 Pre 和 Nex 值，相当于“批量查询符合条件的范围”。
• 树状数组：用来快速计算前缀和，判断区间内是否存在“不满足 Hall 条件”的情况，相当于“一键检查”。
• 离线处理：把查询按 R 排序，逐个处理 R，顺便回答所有相关查询，提高效率。

四、为什么这么做？

• 直接暴力检查每个区间会超时（N 和 Q 都是 1e5 级别）。
• 预处理把每个学生的匹配范围固定，查询时用前缀和快速验证，把复杂度降到 O((N+Q) log N)，能通过大数据。

五、总结

这道题的关键是“把匹配问题转化为范围查询问题”，用 Hall 定理简化条件，再用线段树和树状数组这两个工具快速处理。核心思想就是“预处理+离线查询”，避免重复计算，高效响应每个查询。

要不要我帮你整理一份关键变量和函数的通俗对照表？把代码里的专业术语换成直白解释，帮你更快看懂代码逻辑。