问题分析

这是一个二维偏序统计问题，需要计算：

• 在给定的矩形区域 $[l, r] \times [x, y]$ 内，有多少点对 $(i, j)$ 满足 $i < j$ 且 $p_i < p_j$（即顺序对）
• 所有点的横坐标是 $1$ 到 $n$ 的排列，纵坐标也是 $1$ 到 $n$ 的排列
• 需要高效处理 $m$ 个矩形查询，其中 $n \leq 10^5$, $m \leq 2 \times 10^5$

核心思路

1. 分块策略

• 将序列分成大小为 $B$ 的块（通常 $B \approx \sqrt{n}$）
• 对每个块内部进行预处理，维护块内点的排序信息
• 将查询分为三类：完全在块内、跨块、涉及多个块

2. 预处理优化

• 对每个块内的点按值排序，建立值域到块内排名的映射
• 预处理块内的二维前缀和数组，用于快速计算块内顺序对
• 维护块间的顺序对信息，减少重复计算

3. 查询处理分类

块内查询：

• 查询完全落在一个块内，直接使用预处理信息计算

跨块查询：

• 将查询分解为：左散块 + 中间整块 + 右散块
• 分别计算三部分内部的顺序对和相互之间的顺序对

散块与整块的交互：

• 散块内部：暴力计算顺序对
• 散块与整块：利用预处理信息快速统计
• 整块之间：使用预处理的块间顺序对信息

4. 复杂度平衡

• 块大小 $B$ 的选择平衡了预处理和查询的复杂度
• 通过预处理将 $O(n^2)$ 的暴力算法优化到 $O(n\sqrt{n})$ 级别
• 利用排序和二分查找加速范围查询

算法特点

1. 时间复杂度：$O((n+m)\sqrt{n})$，通过分块平衡复杂度
2. 空间复杂度：$O(n\sqrt{n})$，存储块内预处理信息
3. 适应性强：能处理大规模数据和多种查询类型

解决效果

该分块算法能够高效处理 $n \leq 10^5$, $m \leq 2 \times 10^5$ 的大规模数据，通过巧妙的块划分和预处理技术，在保证正确性的同时实现了亚平方级别的复杂度，成功解决了二维偏序统计问题。