【BestCoder #48】
2024-09-06 14:17:13
与之前一样,秒刷A和B,然后就永远卡在了C
B也因为少看一句话被Hunt掉了
说说C的做法吧(分块大法好
给定一个序列,每次询问区间l-r,求∑(ai^bi),其中bi是指ai在区间中的出现次数,ai是指有在区间中出现的数。
先把官方的正解贴出来:
然后我用自己的话来说一下。。
分块,首先预处理出h(i,j)和g(a,b),各自的复杂度一个为n^1.5,一个多加上快速幂的logn
h的话你可以求出每个块所含有的数 O(块数*块内元素数=n),然后再前缀和累加起来 O(值域*块数=n^1.5)
g的话直接利用正解说的方法暴力求一下 O(块数*块数*块内元素数*计算时间=n^1.5*logn)
对于询问,我们可以将分块完剩余的两端暴力求出各个数的出现次数,然后与中间整块的答案合并 O(块内元素数*计算时间=n^0.5*logn)
对于快速幂所带来的log,我们预处理出所有有可能要计算的幂就行了,用vector存的话空间也不是问题 O(n)
总的复杂度就是O(n^1.5+Q*n^1.5)
最新文章
- ActivityManagerService是如何启动app
- poj.1988.Cube Stacking(并查集)
- Oracle merge
- At_speed_test
- Xcode5 支持 SVN 1.7
- QNX 实时操作系统(Quick Unix)
- 为Widget添加事件
- android SDK 代理配置(东北大学)
- Android应用切换皮肤功能实现
- linux线程之pthread_join
- 自由的Debian
- 【转】windows浏览共享切换用户登录的方法
- linux下lampp(xampp)安装memcached扩展
- poj1321 棋盘(dfs)
- 重拾《 两周自制脚本语言 》- Eclipse插件实现语法高亮
- 【学习总结】Git学习-参考廖雪峰老师教程-期末总结
- QThread的一些使用心得
- 微信公众号开发--.Net Core实现微信消息加解密
- Docker 入门(Mac环境)- part 5 stacks
- 在win和android上同时进行OpenCV程序设计
热门文章
- iOS 实时监测网络状态(通过Reachability)
- motto - question - bodyParser.urlencoded 中设置 extended 为 true 和 false 有什么区别吗?
- 原生js获取页面中所有checkbox
- layer 点击弹出图片
- pywinauto 的使用
- 分析setup/hold电气特性从D触发器内部结构角度
- SpringCloud框架搭建+实际例子+讲解+系列五
- 在WebAPI中调用其他WebAPI
- [WorldFinal 2012E]Infiltration(dfs+图论)
- 笔记-scrapy-Request/Response