1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;

const int MAXN = 510000;
namespace fast_io {
    //...
}using namespace fast_io;

struct Link_Cat_Tree{
    int sum[MAXN];
    int f[MAXN],c[MAXN][2];
    bool rev[MAXN];
    void push_up(int x){
        sum[x] = sum[c[x][0]] + sum[c[x][1]] + 1;
    }
    void reverse(int x){
        if(!x) return;
        swap(c[x][0],c[x][1]);
        rev[x] ^= 1;
    }
    void push_down(int x){
        if(!x) return;
        if(rev[x]){
            reverse(c[x][0]);
            reverse(c[x][1]);
            rev[x] = 0;
        }
    }
    bool noroot(int x){
        return (c[f[x]][0] == x) || (c[f[x]][1] == x);
    }
    void push_all(int x){
        if(!x) return;
        if(noroot(x)) push_all(f[x]);
        push_down(x);
    }
    void rotate(int x){
        int y = f[x],z = f[y],t = (c[y][1] == x),w = c[x][1-t];
        if(noroot(y)) c[z][c[z][1]==y] = x;
        c[x][1-t] = y,c[y][t] = w; 
        if(w) f[w] = y;
        f[y] = x;f[x] = z;
        push_up(y),push_up(x); 
    }
    void splay(int x){
        push_all(x);
        while(noroot(x)){
            int y = f[x],z = f[y];
            if(noroot(y)){
                if((c[y][1]==x)^(c[z][1]==y)) rotate(x);
                else rotate(y);
            }rotate(x);
        }
    }
    void access(int x){
        for(int y = 0;x;x = f[y=x]){
            splay(x);c[x][1] = y;
            push_up(x);
        }
    }
    void makeroot(int x){
        access(x),splay(x),reverse(x);
    }
    int find(int x){
        access(x),splay(x);
        push_down(x);
        while(c[x][0])
            x = c[x][0],push_down(x);
        return x;
    }
    void link(int x,int y){
        makeroot(x);
        if(find(y)!=x)
            f[x] = y;
    }
    void cat(int x,int y){
        makeroot(x);//find == splay
        if(find(y) == x && f[x] == y && !c[x][1])
            f[x] = c[y][0] = 0,push_up(y);
    }
    int query(int u,int v){
        makeroot(v);
        //if(find(v)!=find(u)) return -1;
        access(u);splay(u);
        return sum[u];
    }
    void print(int n){
        for(int i = 1;i<=n;i++){
            printf("%d: sum:%d f:%d c:%d %d r:%d\n",i,sum[i],f[i],c[i][0],c[i][1],int(rev[i]));
        }
    }
};


int n,m,num[MAXN];
Link_Cat_Tree T;
void init(){
    read(n);
    for(int i = 1;i<=n;i++)
        read(num[i]);
    for(int i = 1;i<=n;i++)
        T.link(i,min(i+num[i],n+1));
}
void solve(){
    read(m);
    int op,a,b;
    for(int i = 1;i<=m;i++){
        read(op);read(a);++a;
        if(op == 1)
            print(T.query(a,n+1)-1),print('\n');
        else if(op == 2){
            read(b);
            T.cat(a,min(a+num[a],n+1));
            T.link(a,min(a+b,n+1));
            num[a] = b;
        }
    }
}

int main(){
    init();
    solve();
    flush();
    return 0;
}