关于LCT的问题详见我的LCT总结
思路分析
首先分析一下题意。对于每个弹力装置，有且仅有一个位置可以弹到。把这样的一种关系可以视作边。
然后，每个装置一定会往后弹，这不就代表不存在环么？
于是，一个森林的模型被我们建出来了。
考虑到有修改弹力值的操作，也就是要断边和连边，于是用LCT维护。
思路一
每一个点向它弹到的位置连边。如果被弹飞了，那么这条边就不存在。
查询弹飞的步数，就是查询该点到其所属原树中根节点的路径的\(size\)。
注意此题的一些特性。我们并不需要查询或者更改指定路径\((x-y)\)的信息。
也就是说，我们根本不需要换根！
原来需要换根的\(split,link,cut\)操作，我们可以根据题目特性适当调整一下。
- 查询原本需要\(split\)，我们直接\(access(x),splay(x)\)，输出\(x\)的\(size\)。
- 连边原本需要\(link\)，题目保证了是一棵树，我们直接改\(x\)的父亲，连轻边。
- 断边原本需要\(cut\)，然而我们确定其父亲的位置，\(access(x),splay(x)\)后，\(x\)的父亲一定在\(x\)的左子树中（LCT总结中的性质1），直接双向断开连接。
然后我们发现，程序一下子少了一堆函数（\(pushdown,makeroot,findroot,split,link,cut\)）
代码少，常数小，何乐而不为？
下面贴代码
#include<cstdio>
#include<cstdlib>
#define R register int
#define I inline void
#define G ch=getchar()
#define gc G;while(ch<'-')G
#define in(z) gc;z=ch&15;G;while(ch>'-')z*=10,z+=ch&15,G;
const int N=200009;
int f[N],c[N][2],s[N];
bool r[N];
inline bool nroot(R x){
return c[f[x]][0]==x||c[f[x]][1]==x;
}
I pushup(R x){
s[x]=s[c[x][0]]+s[c[x][1]]+1;
}
I rotate(R x){
R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;
if(w)f[w]=y;f[y]=x;f[x]=z;
pushup(y);
}
I splay(R x){
R y,z;
while(nroot(x)){
y=f[x];z=f[y];
if(nroot(y))
rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
rotate(x);
}
pushup(x);
}
I access(R x){
for(R y=0;x;x=f[y=x])
splay(x),c[x][1]=y,pushup(x);
}//以上是轻量化的LCT板子
int main()
{
register char ch;
R n,m,j,k;
in(n);
for(j=1;j<=n;++j){
s[j]=1;
in(k);
if(j+k<=n)f[j]=j+k;//如果弹飞了就不连边
}
in(m);
while(m--){
gc;
if(ch&1){
in(j);++j;
access(j);splay(j);//直接查询
printf("%d\n",s[j]);
}
else{
in(j);in(k);++j;
access(j);splay(j);
c[j][0]=f[c[j][0]]=0;//直接断边
if(j+k<=n)f[j]=j+k;//直接连边
pushup(j);
}
}
return 0;
}
思路2
把弹飞这种情况也可以视作一个节点（编号可定为\(n+1\)）
如果弹飞了就把\(x\)连到这个点上，于是这个点稳稳地坐住了树根的位置。
查询的时候得到的\(size\)减\(1\)即可。
其它同上。
其实个人认为这样不如上面。动态树本身就定义为维护森林，多了这一个点等于强行把它变成一棵树，可能有点多此一举。。。。。。
代码如下，只贴main函数，因为LCT板子是一样的。。。。。。
int main()
{
register char ch;
R rt,n,m,j,k;
in(n);rt=n+1;
for(j=1;j<=rt;++j)s[j]=1;
for(j=1;j<=n;++j){
in(k);
f[j]=j+k>n?rt:j+k;//与上面不同
}
in(m);
while(m--){
gc;
if(ch&1){
in(j);++j;
access(j);splay(j);
printf("%d\n",s[j]-1);
}
else{
in(j);in(k);++j;
access(j);splay(j);
c[j][0]=f[c[j][0]]=0;
f[j]=j+k>n?rt:j+k;
pushup(j);
}
}
return 0;
}