思路并不难，主要是细节需要注意一下.
在 lct 中，删边要写成：f[lson]=0,lson=0 （因为删 x->y 时 y 不一定是左儿子，y 只是 x 的前驱）
然后 f[lson]=lson=0 这个写法在一些编译器上是错误的（就是你会发现 f[lson] 中这个 lson 会变成 0 )
因为那个错误 tle 了半天 ~
code:
#include <cstdio>
#include <algorithm>
#define N 200006
#define lson t[x].ch[0]
#define rson t[x].ch[1]
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
struct node
{
int ch[2],size,pos,f;
}t[N];
inline int get(int x)
{
return t[t[x].f].ch[1]==x;
}
inline int isrt(int x)
{
return !(t[t[x].f].ch[0]==x||t[t[x].f].ch[1]==x);
}
inline void pushup(int x)
{
t[x].size=t[lson].size+t[rson].size+1;
}
inline void rotate(int x)
{
int old=t[x].f,fold=t[old].f,which=get(x);
if(!isrt(old))
t[fold].ch[t[fold].ch[1]==old]=x;
t[old].ch[which]=t[x].ch[which^1],t[t[old].ch[which]].f=old;
t[x].ch[which^1]=old,t[old].f=x,t[x].f=fold;
pushup(old),pushup(x);
}
inline void splay(int x)
{
int u=x,fa;
while(!isrt(u)) u=t[u].f;
for(u=t[u].f;(fa=t[x].f)!=u;rotate(x))
{
if(t[fa].f!=u)
{
rotate(get(fa)==get(x)?fa:x);
}
}
}
void Access(int x)
{
for(int y=0;x;y=x,x=t[x].f)
{
splay(x);
rson=y;
pushup(x);
}
}
int find(int x)
{
Access(x),splay(x);
while(lson) x=lson;
splay(x);
return x;
}
// 所有边都是有向的（x->y)
void link(int x,int y)
{
if(find(y)==x) t[x].pos=y;
else
{
Access(x),splay(x),t[x].f=y;
}
}
void cut(int x,int y)
{
if(t[x].pos==y) t[x].pos=0;
else
{
int rt=find(x);
Access(x),splay(x);
t[t[x].ch[0]].f=0;
t[x].ch[0]=0;
pushup(x);
if(t[rt].pos&&find(t[rt].pos)!=rt)
{
link(rt,t[rt].pos);
t[rt].pos=0;
}
}
}
int val[N];
int main()
{
// setIO("input");
int i,n,m;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
{
scanf("%d",&val[i]);
if(i+val[i]<1||i+val[i]>n) link(i,n+1);
else link(i,i+val[i]);
}
for(i=1;i<=m;++i)
{
int op;
scanf("%d",&op);
if(op==1)
{
int x;
scanf("%d",&x);
int rt=find(x);
if(rt!=n+1) printf("-1\n");
else printf("%d\n",t[rt].size-1);
}
if(op==2)
{
int x,y;
scanf("%d%d",&x,&y);
if(x+val[x]<1||x+val[x]>n) cut(x,n+1);
else cut(x,x+val[x]);
val[x]=y;
if(x+val[x]<1||x+val[x]>n) link(x,n+1);
else link(x,x+val[x]);
}
}
return 0;
}