🧠 题目名称：二维区间内逆序对查询

🧾 题目描述：

给你一个二维平面上的 $n$ 个点，第 $i$ 个点的坐标是 $(x_i, y_i)$，并且给你 $q$ 个查询。每个查询给定一个矩形区域 $[x_1, x_2] \times [y_1, y_2]$，你需要统计在这个区域内有多少 逆序对 $(i, j)$ 满足：

• $i < j$
• 点 $i$ 和点 $j$ 都在该矩形内
• $x_i < x_j$ 且 $y_i > y_j$

⛓ 输入格式：

python-repl
复制编辑
n q
x_1 y_1
x_2 y_2
...
x_n y_n
l_1 r_1 d_1 u_1
l_2 r_2 d_2 u_2
...
l_q r_q d_q u_q

• 第 1 行输入两个整数 $n$ 和 $q$，表示点数和查询数。
• 接下来 $n$ 行，每行两个整数，表示每个点的坐标。
• 再接下来 $q$ 行，每行四个整数，表示查询矩形的左右上下边界（$x$ 从 $l$ 到 $r$，$y$ 从 $d$ 到 $u$）。

📤 输出格式：

对每个查询输出一行一个整数，表示该区域内满足条件的逆序对数量。

🔒 数据范围：

• $1 \le n \le 10^5$
• $1 \le q \le 10^5$
• $0 \le x_i, y_i \le 10^6$
• 所有坐标值为整数

💡 样例输入：

复制编辑
5 2
1 5
2 4
3 3
4 2
5 1
1 5 1 5
2 4 2 4

✅ 样例输出：

复制编辑
10
3

📘 提示：

• 这是一个高级题目，单次查询暴力是 $O(n^2)$，必须优化。
• 建议使用 ​CDQ 分治​、树状数组+扫描线 或 整体二分 来优化查询。
• 可以考虑将所有查询离线处理，通过对坐标进行排序+维护前缀统计解决逆序对问题。🧠 题目名称：二维区间内逆序对查询 🧾 题目描述： 给你一个二维平面上的 $n$ 个点，第 $i$ 个点的坐标是 $(x_i, y_i)$，并且给你 $q$ 个查询。每个查询给定一个矩形区域 $[x_1, x_2] \times [y_1, y_2]$，你需要统计在这个区域内有多少 逆序对 $(i, j)$ 满足：

$i < j$

点 $i$ 和点 $j$ 都在该矩形内

$x_i < x_j$ 且 $y_i > y_j$

⛓ 输入格式： python-repl 复制 编辑 n q x_1 y_1 x_2 y_2 ... x_n y_n l_1 r_1 d_1 u_1 l_2 r_2 d_2 u_2 ... l_q r_q d_q u_q 第 1 行输入两个整数 $n$ 和 $q$，表示点数和查询数。

接下来 $n$ 行，每行两个整数，表示每个点的坐标。

再接下来 $q$ 行，每行四个整数，表示查询矩形的左右上下边界（$x$ 从 $l$ 到 $r$，$y$ 从 $d$ 到 $u$）。

📤 输出格式： 对每个查询输出一行一个整数，表示该区域内满足条件的逆序对数量。

🔒 数据范围： $1 \le n \le 10^5$

$1 \le q \le 10^5$

$0 \le x_i, y_i \le 10^6$

所有坐标值为整数

💡 样例输入： 复制 编辑 5 2 1 5 2 4 3 3 4 2 5 1 1 5 1 5 2 4 2 4 ✅ 样例输出： 复制 编辑 10 3 📘 提示： 这是一个高级题目，单次查询暴力是 $O(n^2)$，必须优化。

建议使用 CDQ 分治、树状数组+扫描线 或 整体二分 来优化查询。

可以考虑将所有查询离线处理，通过对坐标进行排序+维护前缀统计解决逆序对问题。