描述
- Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。
分析
- 分块, 维护 i 位置的绵羊经过几次弹出该块(f[]), 以及弹出后落在哪个位置(arv[]). 这样就可以在 n√n 的时间内完成本题.
- 遇到查询操作, 则每次 ans 加上 f[i], i 转移到 arv[i], 直到 arv[i] ≥ n
- 遇到修改操作, 则只需维护 该块的 f[] 数组和 arv[] 数组.
- 维护时不用一个点一个点的计算, 而是从后向前倒推.
BZOJ-2002-Bounce弹飞绵羊-分块
原文:http://blog.csdn.net/qq_21110267/article/details/44923291