https://www.luogu.com.cn/problem/P3203

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define int long long
#define fa(x) fa[x]
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
#define notroot(x) lc(fa(x))==x||rc(fa(x))==x
using namespace std;

const int N = 2e5 + 10;

int n, m;
int ch[N][2], fa[N], sz[N], v[N];//左右儿子，父亲，树的大小，权值
bool tag[N];//翻转懒标记

void pushup(int x)
{
    //上传
    sz[x] = sz[lc(x)] + sz[rc(x)] + 1;
}

void pushdown(int x)
{
    //下传
    if (tag[x])
    {
        swap(lc(x), rc(x));
        tag[lc(x)] ^= 1;
        tag[rc(x)] ^= 1;
        tag[x] = 0;
    }
}

void pushall(int x)
{
    //递归下传
    if (notroot(x)) pushall(fa(x));
    pushdown(x);
}

void rotate(int x)
{
    //旋转x
    int y = fa(x), z = fa(y), k = rc(y) == x; //y的右儿是x
    if (notroot(y)) ch[z][rc(z) == y] = x; fa(x) = z; //z的儿是x,x的父是z
    ch[y][k] = ch[x][k ^ 1]; fa(ch[x][k ^ 1]) = y; //y的儿是x的异儿,x的异儿的父是y
    ch[x][k ^ 1] = y; fa(y) = x; //x的异儿是y,y的父是x
    pushup(y);
    pushup(x); //自底向上pushup
}

void splay(int x)
{
    //x伸展到根
    pushall(x); //递归下传
    while (notroot(x))
    { //折线转xx,直线转yx
        int y = fa(x), z = fa(y);
        if (notroot(y)) (rc(y) == x) ^ (rc(z) == y) ? rotate(x) : rotate(y);
        rotate(x);
    }
}

void access(int x)
{
    //打通x到树根的路
    for (int y = 0; x;)
    {
        splay(x); //x转到当前splay的根
        rc(x) = y;  //x的右儿指向下面splay的根
        pushup(x); //更新x的sum
        y = x, x = fa(x); //存x,x爬到上面的splay
    }
}

void makeroot(int x)
{
    //换根
    access(x); //通路
    splay(x);  //伸展
    tag[x] ^= 1; //翻转懒标记
}

void split(int x, int y)
{
    //分离x到y的路径
    makeroot(x); //x换根
    access(y); //y通路
    splay(y);  //y伸展
}

int findroot(int x)
{
    //找根
    access(x);
    splay(x);
    while (lc(x)) pushdown(x), x = lc(x);
    splay(x); //防止卡链
    return x;
}

void link(int x, int y)
{
    //连边
    makeroot(x);
    if (findroot(y) != x) fa(x) = y;
}
void cut(int x, int y)
{
    //断边
    makeroot(x);
    if (findroot(y) == x && fa(y) == x && !lc(y))
        fa(y) = 0, pushup(x);
}

int output(int x, int y)
{
    split(x, y);
    return sz[y] - 1;
}

signed main() 
{
    int n, m;
    cin >> n;
    for (int i = 1; i <= n + 1; ++i) sz[i] = 1;
    for (int i = 1; i <= n; ++i) 
    {
        cin >> v[i];
        if (i + v[i] <= n) link(i, i + v[i]);
        else link(i, n + 1);
    }

    cin >> m;
    while (m--) 
    {
        int opt, i;
        cin >> opt >> i;
        i++;

        if (opt == 1) cout << output(i, n + 1) << endl;
        else 
        {
            int k;
            cin >> k;
            cut(i, i + v[i] <= n ? i + v[i] : n + 1);
            link(i, i + k <= n ? i + k : n + 1);
            v[i] = k;
        }
    }
    return 0;
}