题意：
给你n个编号1到N的洞(N
1.0 a b。把a号洞的po改成b
思路：
假设题目没有改动操作。这题就会非常easy。
我们仅仅须要把每一个洞的出界点和弹跳数预处理出来就能够了。如今关键是怎么处理改动操作。假设还是依照上述预处理方式肯定时间复杂度下不来。
所以我们要想办法使每次改动操作更新尽量少的信息。于是能够想到分块处理。就是把整个序列分成sqrt(N)块。序列中每一个节点记录next[i]表示i结点要跳到下个块的位置。ed[i]表示放到i号洞时的出界位置。st[i]表示。
i跳到下个块须要的步数。这样预处理后每次改动操作仅仅会影响同块内且标号比当前小的位置的信息。
所以最多改动sqrt(n)个位置的信息。对于每次查询操作。因为结点指针仅仅会指向不同的块所以仅仅须要顺着指针统计一遍就好了。最多跳sqrt(n)次。
总时间发杂度O(M*sqrt(N))在能够接受的范围内。
具体见代码：
Original: https://www.cnblogs.com/gccbuaa/p/7401143.html
Author: gccbuaa
Title: codeforces 13EE. Holes(分块&动态树)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/551790/
转载文章受原作者版权保护。转载请注明原作者出处！