1. 题目

传送门= ̄ω ̄=

2. 题解

比较弱智的模板题
听说可以用分块做
然而我们是来做lct的模板题的呀!
不难发现题目中隐藏了一棵树!
如果能从i跳到j,那么就设j为i的父亲(在树上)
设所有出界了的位置的编号都为n+1(就好像在n+1的位置竖了一面墙,你弹上去,pia,就掉下来啦!)
然后这样子对于询问位置i要弹几次弹出也就是询问节点i的深度啦!
因为有连接、断开,因此用lct(雾)
只要实现link和cut就行了,询问深度的话。。。
询问点a,先evert (n+1),让n+1(出界节点)成为根,再access (a),让n+1和a在一个链上(一个splay中),然后splay (a),把a旋到根,最后答案就是a的子树大小

代码: