请选择 进入手机版 | 继续访问电脑版

莫队全家桶

[复制链接]
太阳神鹰 发表于 2021-1-3 12:17:13 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
编号名称实现简介时间复杂度1平凡莫队①                                             O                               (                               n                                           n                                          )                                      O(n \sqrt n)                        O(nn                                           ​)2带修莫队②                                             O                               (                                           n                                               5                                     3                                                      )                                      O(n^{\frac 5 3})                        O(n35​)3在线莫队③                                             O                               (                               n                                           n                                          )                                      O(n \sqrt n)                        O(nn                                           ​)4回滚莫队④                                             O                               (                               n                                           n                                          )                                      O(n \sqrt n)                        O(nn                                           ​)5树上莫队⑤                                             O                               (                               n                                           n                                          )                                      O(n \sqrt n)                        O(nn                                           ​)6高维莫队⑥                                             O                               (                                           n                                               2                                     −                                                   1                                        w                                                                          O(n^{2-\frac 1 w}                        O(n2−w1​)7高维带修莫队⑦                                             O                               (                                           n                                               2                                     −                                                   1                                                       w                                           +                                           1                                                                                        O(n^{2-\frac 1 {w+1}}                        O(n2−w+11​)①: 左端点差别块按左端点排序,否则按右端点排序
②: 取块长为                                       n                                   2                            3                                           n^{\frac 2 3}               n32​,与平凡莫队相比差别点为,如果左右端点均同块则按之前的操纵次数排序
③: 预处理惩罚每一个段边界,每次查询的时候只需要查询小段,小段与大段组合的贡献,可以接纳其他数据结构维护
④: 对于所有左端点所在块相同的询问右端点升序,所以可以维护一个序列,每次向右添加,对于每次询问分别将左端点往左拉再拉返来,制止了打消操纵
⑤: 按照欧拉序,分类讨论两种情况转化为序列上的莫队
⑥:                               w                          w               w指端点的数量
⑦: 略

来源:https://blog.csdn.net/Cherrt/article/details/112060967
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )