首页 > 其他 > 详细

Sqrt Tech

时间:2020-01-18 20:51:53      阅读:94      评论:0      收藏:0      [点我收藏+]

回滚莫队

用来处理一类区间扩张容易而收缩难的莫队问题。

大概的思路如下:
还是按莫队的方法排序(不要奇偶性优化),把所有询问按照左端点所在块分类处理。
对于左端点在同一个块\([L,R]\)的,先把右端点也在\([L,R]\)内的暴力处理。
而其它询问的右端点必定递增,因此我们可以实时处理出\([R,r]\)的区间信息,每次把左端点从\(R\)移到\(l\)
可以发现这样做我们的复杂度还是\(O(n\sqrt n)\)的,并且只需要支持区间扩张了。

例题:Link,先离散化一下然后随便搞搞就完事了。

Sqrt Tech

原文:https://www.cnblogs.com/cjoierShiina-Mashiro/p/12210004.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!