思路:
- 发现直接去存所有的数,一定会超时超空间
- 那么如何去get到某个数呢? 二分 (遇到第K大, 一般也是利用二分处理)
- 二分某个数看他是 第几大, 枚举ai ,然后判断相应的bi有多少个,
- 这里在线直接判断bi是logn的
- 因此要先预处理,利用捅记录数的次数然后利用前缀和处理, 这样就是 O1的
- 因为是要求个数,所以用这个桶去计数
乘法 (20200 CCPC Wannafly Winter Camp Day1) (二分,在线->离线预处理思想优化时间复杂度,桶+前缀和)
发布时间 2023-03-30 21:49:13作者: VxiaohuanV