首页 > 代码库 > 【BZOJ】【3052】【WC2013】糖果公园
【BZOJ】【3052】【WC2013】糖果公园
树分块
老早(大约一个月以前?)就听说这道神题了……orz rausen
一直拖到现在才做……发现还是不会呢= = 只好也去Orz了Hzwer和zky
http://hzwer.com/5250.html http://blog.csdn.net/iamzky/article/details/42125999这个树上莫队真的蛮神奇的……
1.对于每个查询,记录它是在第几次修改之后的;
2.以左端点所在块为第一关键字、右端点所在块为第二关键字、时间(第几次修改之后的查询)为第三关键字进行排序;
3.对于每个查询,先进行时间上的移动(这个只需对变化了的点进行单点修改即可,有点小Z的袜子中 +1-1的感觉)再进行查询序列的移动(用之前讲的vfk的方法……)至于第二步就跟普通的树分块一样了么……
注意:由于时间移动既有向前也有向后的,所以除了要记录是把哪个点变成了什么糖果,还要记录变化前的原来的状态(时光回溯时用)(用“时光回溯”这个名字是不是十分高大上~~)
【BZOJ】【3052】【WC2013】糖果公园
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。