RainAir
My OI Blog
RainAir
「BZOJ2002」「HNOI2010」弹飞绵羊

题目描述

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

题解

LCT 裸题。
我们不妨设一个超级点 $T$,如果在某一个装置会被弹飞的话我们就把这个装置与 $T$ 链接,否则就连到能连的那个装置上。注意到题目保证弹力系数为正整数,所以这样连会得到一个森林,用 LCT 维护一下每个森林的 $size$,查询的时候直接把这个点和超级点拉到一个路径上询问 $size$ 就可以了。
修改操作也很好做……首先断开原来这个点和其他点的连边,然后按照修改后的系数连就可以了。
时间复杂度 $O(n log^2 n)$

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/435
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

  • https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=80&d=mm&r=g
    RainAir博主

    这个题好模板啊…..希望省选都是这样的题就好了QAQ

    10月前回复

RainAir

「BZOJ2002」「HNOI2010」弹飞绵羊
题目描述 题目链接 某天,Lostmonkey 发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置,每…
扫描二维码继续阅读
2019-01-29
标签
近期评论