范围 (l, r) 中小于 'x' 的元素数

Number of elements less than 'x' in a range (l, r) both inclusive

给定一个整数数组,并且只有一种查询类型。

查询 - (L, R, X)

查找范围 (L, R) 中小于 'X' 的元素。

PS:所有查询都是事先提供的,即我们需要设计一个离线算法来回答所有查询。

这可以借助线段树和向量来完成。在线段树的每个节点维护一个向量。在构建树的同时,维护线段树每个节点的向量中的排序顺序。

应用二进制搜索在处理查询的线段树的每个节点处查找少于 'X' 的元素数。

int count = upper_bound(v.begin(), v.end(), X) - v.begin();

上面post也把这个想法描述得很漂亮。