【每日一题】4月30日题目精讲 离线+树状数组

题号 NC19427
名称 换个角度思考
来源 牛客小白月赛9
戳我进入往期每日一题汇总贴~
往期每日一题题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

各种方法都可以做，比如说主席树莫队什么的，下方题解里也基本上都出现了，给大家点赞~
讲一个最简单的方法，离线+树状数组。（顺便说一下考虑用离线来处理问题的思路）
不离线直接查询的麻烦在于查询的时候有两个东西都是未知的——区间左右端点和x。我们考虑离线，是要通过离线相关的操作把这询问有关的两个不同性质变得只问一个，也即，如果我们要问区间[l,r]有多少个数就保证当前所有数都是小于等于x的，如果要问小于等于x有多少个数，就要保证目前只有区间[l,r]里面的东西。
先看第一种：在保证当前所有数都是小于等于x的情况下询问区间[l,r]有多少个数。
很简单，我们按照x对询问排序，对ai也排序，每次询问当前[l,r,x]之前把ai小于等于x的ai加入他对应的位置（只需要对应位置点数+1就行)，然后询问[l,r]区间有多少个数。
再看第二种：在保证当前数都是[l,r]区间的情况下查询小于等于x的数字个数。
这个貌似没法做，因为区间可能交叉，但是实际上我们可以离线的时候把[l,r]区间转化为[1,l-1]和[1,r]两个区间，这样子问题就变成，在前若干个数字里面求小于等于x的数字个数，一个值域树状数组就可以了！

看完邓老师的题解，记得自己去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目5月7日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴