某道 Ynoi
Mobius127
·
·
题解
P9999
好菜啊这个题，为什么有黑？
考虑操作一个点 x 时，除 1-x 链上的点其它点都会向上移动，链上的点则会向 x 移动，考虑使用树剖把暴力移动的复杂度均摊下来。
离线询问做扫描线，考虑把每个询问当成一个在 x 的草履虫（？），每次让点向 a_{i} 移动时，考虑给所有草履虫先打上一个向上 +1 的标记，再给 a_{i} 的祖先上的草履虫 -1。考察每个草履虫与当前所在重链链头的距离，爆 far 掉 0 了就暴力移动到父节点。
对于 a_{i} 的祖先，暴力遍历每条重链打 tag 就好。多个点到了一起就并查集缩起来就好了。
不难得到链外操作减少 n-\log n 势能，链内操作最多加 \log n 势能，复杂度为 O(n\log n f(n))，f(n) 是一个判定重链的 DS，可以轻松做到 f(n)=\log n。
晚修回去考虑了一下实现细节，FHQ-treap 以重剖标号序作为比较字，维护 p,dfn,u,d 分别表示询问的编号，这个询问现在所在的点的重剖序，u 表示到链头的距离。操作 a_i 时，就先将 1-a_{i} 的 \log n 段单独拿出来，先把这些段恰好为链尾的（即 \max dfn=endp，维护子树 dfn 最大值即可）拿出来，然后整体打 dfn+1,u+1 的 tag。对于剩下的部分，则是先把 u=0 的拿出来，对于剩下的打 dfn-1,u-1 的 tag 即可。