【模板】离线二维数点题解

思路

把每个序列元素看成二维点 $(i,a_i)$。询问要求统计横坐标位于 $[l,r]$、纵坐标不超过 $x$ 的点数。

按值从小到大扫描。扫描到值 $v$ 时，把所有满足 $a_i=v$ 的位置 $i$ 加入位置 Fenwick 树。处理阈值为 $x$ 的询问时，树中恰好保存所有 $a_i\le x$ 的位置，因此区间和就是答案。由于值域不超过 $2\times10^6$，可以直接按值建立桶，避免排序。

做法

1. 按取值把每个序列位置放入对应的值桶。
2. 按阈值把每个询问放入对应的询问桶，并保留原编号。
3. 从小到大扫描值域；先把当前值的全部位置加入 Fenwick 树，再回答当前阈值桶中的询问。
4. 按原编号依次输出答案。

正确性证明

扫描完值 $1,2,\ldots,x$ 后，位置 $i$ 在 Fenwick 树中的值为一，当且仅当 $a_i\le x$。这是因为每个位置只会在扫描到其唯一取值时加入一次，且之后不会删除。

因此，Fenwick 树在 $[l,r]$ 上的区间和，恰好等于满足 $l\le i\le r$ 且 $a_i\le x$ 的位置数，与询问定义一致。所有询问都在扫描到其阈值时处理，故算法输出全部正确答案。

复杂度

设值域上界为 $V=2\times10^6$。建桶和扫描值域为 $O(n+m+V)$，每个位置加入和每个询问查询各需 $O(\log n)$，总时间复杂度为 $O((n+m)\log n+V)$，空间复杂度为 $O(n+m+V)$。