Description：

在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$ ，当绵羊达到第 $i$ 个装置时，它会往后弹 $k_i$ 步，达到第 $i+k_i$ 个装置，若不存在第 $i+k_i$ 个装置，则绵羊被弹飞。绵羊想知道当它从第 $i$ 个装置起步时，被弹几次后会被弹飞。可以修改某个弹力装置的弹力系数。

Solution：

如果用 $LCT$ 的话将点 $i$ 和点 $i+k_i$ 连起来，则 $makeroot(n+1),access(i),splay(i)$ 后 $root$ 的 $size-1$ 就是答案。

还可以分块，对每个点维护第一次跳到块外的次数 $f[i]$ 和跳到的位置 $to[i]$ ，对于查询不停向后跳并累加 $f[i]$ ，修改时暴力重构这个块这个位置之前的点。

Code：

$LCT$ ：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

#define MAXN 200010

int n,m;

struct node

{

    int fa,c[2],siz,w;

    bool rev;

    node(){fa = c[0] = c[1] = siz = 0;rev = false;}

}t[MAXN];

void maintain(int k){t[k].siz = t[t[k].c[0]].siz + t[t[k].c[1]].siz + 1;}

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

void pushdown(int k)

{

    if(!t[k].rev)return;

    t[t[k].c[0]].rev ^= 1;t[t[k].c[1]].rev ^= 1;

    swap(t[k].c[0],t[k].c[1]);

    t[k].rev = false;

    return;

}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;}

void rotate(int x)

{

    int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

    if(!isroot(y))t[z].c[fy] = x;

    t[x].fa = z;

    connect(t[x].c[fx^1],y,fx);

    connect(y,x,fx^1);

    maintain(y);maintain(x);

    return;

}

stack<int> s;

void splay(int x)

{

    s.push(x);

    for(int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

    while(!s.empty()){pushdown(s.top());s.pop();}

    while(!isroot(x))

    {

        int y = t[x].fa;

        if(isroot(y)){rotate(x);break;}

        if(id(x) == id(y)){rotate(y);rotate(x);}

        else{rotate(x);rotate(x);}

    }

    return;

}

void access(int k){for(int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;}

void link(int x,int y){makeroot(x);t[x].fa = y;}

void cut(int x,int y){makeroot(x);access(y);splay(y);t[y].c[0] = t[x].fa = 0;}

int main()

{

    scanf("%d",&n);

    for(int i = 1;i <= n;++i)

    {

        scanf("%d",&t[i].w);

    }

    for(int i = 1;i <= n;++i)

    {

        link(i,min(n + 1,i + t[i].w));

    }

    scanf("%d",&m);

    int a,b,c;

    for(int i = 1;i <= m;++i)

    {

        scanf("%d",&a);

        if(a == 1)

        {

            scanf("%d",&b);++b;

            makeroot(n + 1);access(b);splay(b);

            printf("%d\n",t[b].siz - 1);

        }

        else

        {

            scanf("%d%d",&b,&c);++b;

            cut(b,min(n + 1,b + t[b].w));

            t[b].w = c;

            link(b,min(n + 1,b + t[b].w));

        }

    }

    return 0;

}

分块：

// luogu-judger-enable-o2

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 200010

int k[MAXN],f[MAXN],to[MAXN];

int siz,tot,L[MAXN],R[MAXN],belong[MAXN];

inline void build_block(int l,int r,int p)

{

    L[p] = l;R[p] = r;

    for(register int i = l;i <= r;++i)belong[i] = p;

    return;

}

inline void maintain(int p,int l)

{

    for(register int i = l;i >= L[p];--i)

    {

        if(i + k[i] > R[p]){f[i] = 1;to[i] = i + k[i];}

        else{f[i] = f[i + k[i]] + 1;to[i] = to[i + k[i]];}

    }

    return;

}

inline int query(int p)

{

    int ans = 0;

    while(p <= n)

    {

        ans = ans + f[p];

        p = to[p];

    }

    return ans;

}

inline int read()

{

    int res = 0;

    char c = getchar();

    while(!isdigit(c))c = getchar();

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res;

}

int main()

{

    scanf("%d",&n);

    for(register int i = 1;i <= n;++i)

        k[i] = read();

    tot = siz = sqrt(n);

    for(register int i = 1;i <= tot;++i)

    {

        build_block((i - 1) * siz + 1,i * siz,i);

        maintain(i,i * siz);

    }

    if(siz * siz < n)

    {

        ++tot;

        build_block(R[tot - 1] + 1,n,tot);

        maintain(tot,n);

    }

    scanf("%d",&m);

    int type,a,b;

    for(register int i = 1;i <= m;++i)

    {

        type = read();

        if(type == 1)

        {

            a = read();

            ++a;

            printf("%d\n",query(a));

        }

        else

        {

            a = read();b = read();

            ++a;

            k[a] = b;

            maintain(belong[a],a);

        }

    }

    return 0;

}