题意理解

我们有 $N$ 个学生，每个学生有两个分数：数学 $S_i$，信息学 $T_i$。

T 教授标准：

数学 $\ge A$ 且 信息学 $\ge B$。

I 教授标准：

数学 + 信息学 $\ge C$。

通过条件：同时满足 T 教授和 I 教授的标准。

对于 $Q$ 个询问 $(X_j, Y_j, Z_j)$，即 $(A, B, C)$，求满足条件的学生人数。

---

问题形式化

对于每个询问 $(A, B, C)$，我们要数出满足以下条件的学生 $i$ 的个数：

$$\begin{cases} S_i \ge A \\ T_i \ge B \\ S_i + T_i \ge C \end{cases} $$

---

直接暴力解法

最直接的方法：对每个询问，遍历所有学生检查条件。 时间复杂度：$O(NQ)$，在 $N, Q \le 10^5$ 时不可行。

优化思路

我们需要预处理学生数据，以便快速回答每个查询。

1. 三维条件分析

条件：

$S_i \ge A$

$T_i \ge B$

$S_i + T_i \ge C$

可以看作三维空间 $(S, T, S+T)$ 中的点，查询是一个三维矩形（实际是半空间）的计数问题。

2. 离线处理 + 排序 + 数据结构

一个常见技巧：将 $S_i$ 和 $T_i$ 离散化，因为值域很大但数量不多。

设 $U = S_i + T_i$。

查询条件等价于：

$S_i \ge A$

$T_i \ge B$

$U_i \ge C$

3. 二维偏序思路

我们可以固定一个维度，用离线方法处理。

例如： 将学生按 $S_i$ 从大到小排序，将查询按 $A$ 从大到小排序。 这样，当我们处理一个查询 $(A, B, C)$ 时，所有 $S_i \ge A$ 的学生已经加入某个数据结构，我们只需要在这个集合中数出满足 $T_i \ge B$ 且 $U_i \ge C$ 的学生个数。

4. 进一步转化

对于 $T_i \ge B$ 且 $U_i \ge C$ 的计数，可以看作二维平面 $(T, U)$ 上的矩形查询（$T \ge B, U \ge C$）。

这是一个典型的二维偏序计数问题，可以用 二维树状数组（Fenwick Tree） 或 线段树套线段树 解决。

5. 具体步骤

离散化 $T_i$ 和 $U_i$（因为 $U_i = S_i + T_i$ 值域是 $[0, 2\times 10^9]$，但不同值最多 $N$ 个）。

将学生按 $S_i$ 降序排序。

将查询按 $A$ 降序排序。

用一个二维树状数组（或线段树）维护 $(T, U)$ 平面上的点。

双指针：

对于当前查询 $(A, B, C)$，将所有 $S_i \ge A$ 且尚未加入数据结构的学生加入。

在数据结构中查询 $T \ge B$ 且 $U \ge C$ 的点数。

输出答案。

6. 数据结构查询

我们维护的二维 BIT 是：

第一维是 $T$（离散化后）

第二维是 $U$（离散化后）

加入一个学生 $(T, U)$ 时，在 BIT 的对应位置 $+1$。

查询 $T \ge B$ 且 $U \ge C$ 的点数，可以转化为：

$$总点数−(T < B 或 U < C 的点数)$$

更简单：二维 BIT 通常支持矩形和，我们可以直接求 $[B, \infty) \times [C, \infty)$ 的和。

7. 离散化细节

$T$ 的离散化：所有 $T_i$ 和所有查询的 $B$ 一起离散化。

$U$ 的离散化：所有 $U_i$ 和所有查询的 $C$ 一起离散化。

这样保证查询时能找到对应的离散化坐标。

8. 时间复杂度

离散化：$O((N+Q)\log(N+Q))$

排序：$O(N\log N + Q\log Q)$

二维 BIT 操作：每次插入和查询 $O(\log N \log N)$

总复杂度：$O(N\log^2 N + Q\log^2 N)$，可接受。

---

核心公式

对于查询 $(A, B, C)$，答案是：

$$\sum_{i=1}^N [S_i \ge A \wedge T_i \ge B \wedge S_i + T_i \ge C] $$

其中 $[P]$ 是指示函数，条件 $P$ 成立时为 1，否则为 0。

---

总结

本题的关键在于：

1.将条件转化为三维空间中的半空间查询。

2.通过离线排序降维。

3.使用二维数据结构维护剩余二维偏序查询。

4.离散化处理大值域。

这样就可以在 $O(N\log^2 N + Q\log^2 N)$ 时间内解决大规模数据。