题意分析

我们有 $n$ 个巧克力，每个巧克力是二维平面上的点 $(x, y)$，带权值 $h$。

有 $m$ 个询问，每个询问给出 $(a, b, c)$，要求计算所有满足 [ a x + b y < c ] 的巧克力的 $h$ 值之和。

---

核心难点

• $n, m \le 50000$，需要高效查询。
• $a, b, x, y$ 范围很大（$[-10^9, 10^9]$），且可为负数。
• 查询是半平面形式 $a x + b y < c$，但 $a, b$ 符号不确定，所以方向任意。

---

解法思路

1. 暴力法

对每个询问，遍历所有巧克力，检查条件并累加 $h$。
复杂度 $O(n m)$，不可行。

---

2. 半平面查询问题

查询 $a x + b y < c$ 等价于点在直线 $a x + b y = c$ 的某一侧。

由于 $a, b$ 可正可负，这个半平面可能是任意方向的。

对于这种任意方向半平面点权和查询，常用方法有：

• K-D Tree 配合剪枝
• 半平面扫描（但这里 $m$ 很大，难做）

---

K-D Tree 解法

K-D Tree 可以在 $O(\sqrt{n})$ 平均时间内完成矩形区域查询，但这里是半平面查询，需要特殊处理。

---

关键观察

我们可以将 $a x + b y < c$ 看作线性函数 $f(p) = a x + b y$ 的值小于 $c$。

在 K-D Tree 查询时，对每个节点维护其包围盒（$x_{\min}, x_{\max}, y_{\min}, y_{\max}$），并计算 $f(p)$ 在包围盒上的最小值和最大值。

---

剪枝策略

对于当前节点：

1. 如果包围盒的 $f_{\max} < c$，则整个节点内的点都满足条件，直接返回该子树权值和。
2. 如果包围盒的 $f_{\min} \ge c$，则整个节点内的点都不满足条件，直接返回 $0$。
3. 否则递归查询左右子树。

---

复杂度

• 建树：$O(n \log n)$
• 单次查询：最坏 $O(n)$，但随机数据下约 $O(\sqrt{n})$，且剪枝有效。
• 总复杂度：$O(m \sqrt{n})$，在 $n,m=50000$ 时勉强可过（约 $3.5 \times 10^7$ 操作）。

---

算法步骤

1. 读入 $n, m$ 和巧克力数据 $(x, y, h)$。
2. 构建 K-D Tree（按 $x, y$ 交替划分），每个节点维护：
   • 包围盒 $[x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}]$
   • 子树 $h$ 和
3. 对每个查询 $(a, b, c)$：
   • 在 K-D Tree 上做 DFS，用上述剪枝。
   • 对叶子节点直接检查 $a x + b y < c$。
4. 输出每个查询的结果。

---

样例验证

输入：

3 3
1 2 5
3 1 4
2 2 1
2 1 6
1 3 5
1 3 7

巧克力：

• $P_1=(1,2), h=5$
• $P_2=(3,1), h=4$
• $P_3=(2,2), h=1$

查询 1: $a=2, b=1, c=6$
条件 $2x + y < 6$：

• $P_1$: $2\times 1 + 2 = 4 < 6$ ✓
• $P_2$: $6 + 1 = 7 \ge 6$ ✗
• $P_3$: $4 + 2 = 6 \ge 6$ ✗
  和 = 5，输出 5。

查询 2: $a=1, b=3, c=5$
条件 $x + 3y < 5$：

• $P_1$: $1 + 6 = 7 \ge 5$ ✗
• $P_2$: $3 + 3 = 6 \ge 5$ ✗
• $P_3$: $2 + 6 = 8 \ge 5$ ✗
  和 = 0，输出 0。

查询 3: $a=1, b=3, c=7$
条件 $x + 3y < 7$：

• $P_1$: $7 \ge 7$ ✗
• $P_2$: $6 < 7$ ✓
• $P_3$: $8 \ge 7$ ✗
  和 = 4，输出 4。

与样例输出一致。

---

优化技巧

1. 轮换划分：K-D Tree 按 $x$ 和 $y$ 轮换划分，保持平衡。
2. 启发式选择划分点：选中位数作为划分点，使树平衡。
3. 提前计算极值：对每个节点预计算 $a x + b y$ 的最小最大值（在查询时根据 $a,b$ 计算，因为 $a,b$ 每次不同）。
   • 对包围盒 $[x_l, x_r] \times [y_l, y_r]$，$f_{\min} = \min(a x_l, a x_r) + \min(b y_l, b y_r)$（注意 $a,b$ 符号）
   • 同理 $f_{\max} = \max(a x_l, a x_r) + \max(b y_l, b y_r)$

---

总结

这道题通过 K-D Tree 的包围盒极值剪枝，将半平面查询转化为区域查询，利用 $O(\sqrt{n})$ 的平均复杂度处理大规模数据，是 K-D Tree 在半平面查询中的典型应用。