左侧lower_bound

数据n ,m 找从左到右第一次<m的位置

1
2
3

7
5
10 5 8 4 5 9 3 

利用权值线段树类似的思想,桶里入每个数字第一次出现的位置

1
2

0 0 7 4 2 0 0 3 6 1
1 2 3 4 5 6 7 8 9 10

如果我们想要找第一个$<5$的位置,那只要需要找区间$[1,4]$内的最小值,注意这里0表示无穷大

1
2

[0 0 7 4] 2 0 0 3 6 1
[1 2 3 4] 5 6 7 8 9 10

这里最小的是4,可以说在位置4之前的数都是$\geq 5$,同时找到了最后一个$\geq 5$的位置

使用数理逻辑证明这个方式是正确的

所以问题转化为线段树

1 相关题解

暂无相关题解