Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 2002: [Hnoi2010]Bounce 弹飞绵羊

题目链接

传送门

Description

某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。

Input

第一行包含一个整数n,表示地上有n个装置,装置的编号从0到n-1,接下来一行有n个正整数,依次为那n个装置的初始弹力系数。第三行有一个正整数m,接下来m行每行至少有两个数i、j,若i=1,你要输出从j出发被弹几次后被弹飞,若i=2则还会再输入一个正整数k,表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000,对于100%的数据n<=200000,m<=100000

Output

对于每个i=1的情况,你都要输出一个需要的步数,占一行。

Sample Input

4

1 2 1 1

3

1 1

2 1 1

1 1

Sample Output

2

3

想说的话

这道题很有纪念意义啊
作为非模板题的lct和分块第一题
完了吧
bzoj上面的题号还是2002

题解I

首先分析一下题意。对于每个弹力装置,有且仅有一个位置可以弹到。把这样的一种关系可以视作边。
然后,每个装置一定会往后弹,这不就代表不存在环么?
于是,一个森林的模型被我们建出来了。
考虑到有修改弹力值的操作,也就是要断边和连边,于是用LCT维护。
每一个点向它弹到的位置连边。如果被弹飞了,那么这条边就不存在。
查询弹飞的步数,就是查询该点到其所属原树中根节点的路径的size
其实这样的话很多的操作都可以省略了
但是由于我要练习lct
所以我敲了所有的操作

代码I

题解II

把弹飞这种情况也可以视作一个节点(编号可定为n+1)
如果弹飞了就把x连到这个点上,于是这个点稳稳地坐住了树根的位置。
查询的时候得到的size减1即可。其它同上。
其实个人认为这样不如上面。动态树本身就定义为维护森林,多了这一个点等于强行把它变成一棵树,可能有点多此一举。。。。。。

代码II

题解III

先把所有n个点分成sqrt(n)块,然后记录每一块的左右端点。
对于每个点,记录两个量:一个是它要弹几次才能出它所在的这个块,另外一个是它弹出这个块后到哪个点。
则先造出所有块,并且O(N)循环造好上述两个量
每次询问和修改的复杂度均为O(sqrt(N))(询问就往后一块一块推,修改就把这一整块的所有点都改一遍)

代码III

做法分析


最上面的那个是分块卡常
第二个是分块正常
第三个是lct卡常
第四个是lct正常
从时间来看十个点两者的差距不算大
内存什么的也基本一样
但是代码长度啊。。。。。。
所以说内存角度不用考虑
从时间和代码长度上面来权衡
其实我更推荐分块
但是平时练习的时候就无所谓了
总之自行选择就行了

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏