题目大意

有 $N$ 架飞机，第 $i$ 架从 $(0,A_i)$ 飞到 $(X,B_i)$，有干扰值 $C_i$。一架飞机在某个 $x$ 坐标处会被所有在该 $x$ 坐标处高于它的飞机遮挡，遮挡值为这些飞机干扰值之和。

给定 $Q$ 个询问：飞机 $P_i$ 在 $x \in [S_i, S_i+K]$ 区间内，可能受到的最大遮挡值是多少？

算法思路

核心思想

扫描线 + 线段树，通过求飞机航线的交点来划分区间，在每个区间内遮挡关系不变。

关键观察

对于两架飞机 $i$ 和 $j$，它们在某个 $x$ 坐标处的高度关系会发生变化，当且仅当它们的航线相交

交点 $x$ 坐标可以通过解直线方程求得

在相邻交点之间的区间内，飞机之间的高低顺序保持不变

算法步骤

1. 预处理交点

对每架飞机 $i$（作为被遮挡的飞机）：

计算它与其他所有飞机 $j$ 的交点 $x$ 坐标

如果航线平行且 $i$ 始终在 $j$ 下方，则 $j$ 始终遮挡 $i$

如果航线相交，在交点前后遮挡关系会翻转

2. 构建事件序列

将所有交点作为关键点

在每个关键点处记录遮挡值的变化量

对关键点排序后求前缀和，得到每个区间内的总遮挡值

3. 处理查询

对每个查询 $[S_i, S_i+K]$，找到它覆盖的关键点区间

用线段树求出该区间内的最大遮挡值

算法流程

读入数据：飞机航线和查询

对每架飞机 $i$：

生成与其他飞机的交点事件

构建遮挡值变化序列

排序并求前缀和

用线段树维护区间最大值

处理查询：

二分查找查询区间对应的关键点范围

线段树查询最大值

输出答案

复杂度分析

预处理：$O(N^2 \log N)$，每对飞机求交点并排序

查询处理：$O(Q \log N)$，二分 + 线段树查询

空间复杂度：$O(N^2)$，存储所有交点事件

总结

本题是计算几何 + 区间查询的综合问题：

交点计算：通过解直线方程确定遮挡关系变化点

扫描线思想：利用关键点划分区间，保证区间内关系不变

线段树应用：高效查询任意区间内的最大遮挡值

事件处理：通过加减法维护遮挡值的变化

这种"几何关系分析 + 区间最值查询"的方法适用于许多涉及线性关系和区间查询的问题，体现了计算几何与数据结构的有机结合。