某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
题解:lct操作，对于可以从i一步到i+a[i]我们连一条边（如果i+a[i]>n那么就变成n+1），问题就变成了，i到n+1的最短路，每次更新先把原来的边cut，然后link上新边即可，（刚开始数组开小了一直t，还以为lct写搓了= = ）/************************************************************** Problem: 2002 User: walfy Language: C++ Result: Accepted Time:1740 ms Memory:6772 kb****************************************************************/ //#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//#pragma GCC optimize("unroll-loops")#include #define fi first#define se second#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define vi vector #define mod 1000000007#define ld long double#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pil pair #define pli pair #define pii pair #define cd complex #define ull unsigned long long#define base 1000000000000000000#define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double eps=1e-6;const int N=200000+10,maxn=5000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; struct LCT{ int fa[N],ch[N][2],rev[N],sz[N],q[N]; inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} inline void pushup(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;} inline void pushdown(int x) { if(rev[x]) { rev[x]=0;swap(ch[x][0],ch[x][1]); rev[ch[x][0]]^=1,rev[ch[x][1]]^=1; } } inline void Rotate(int x) { int y=fa[x],z=fa[y],l,r; if(ch[y][0]==x)l=0,r=l^1; else l=1,r=l^1; if(!isroot(y)) { if(ch[z][0]==y)ch[z][0]=x; else ch[z][1]=x; } fa[x]=z;fa[y]=x;fa[ch[x][r]]=y; ch[y][l]=ch[x][r];ch[x][r]=y; pushup(y);pushup(x); } inline void splay(int x) { int top=1;q[top]=x; for(int i=x;!isroot(i);i=fa[i])q[++top]=fa[i]; for(int i=top;i;i--)pushdown(q[i]); while(!isroot(x)) { int y=fa[x],z=fa[y]; if(!isroot(y)) { if((ch[y][0]==x)^(ch[z][0]==y))Rotate(x); else Rotate(y); } Rotate(x); } } inline void access(int x){for(int y=0;x;y=x,x=fa[x])splay(x),ch[x][1]=y,pushup(x);} inline void makeroot(int x){access(x),splay(x),rev[x]^=1;} inline int findroot(int x){access(x),splay(x);while(ch[x][0])x=ch[x][0];return x;} inline void split(int x,int y){makeroot(x),access(y),splay(y);} inline void cut(int x,int y){split(x,y);if(ch[y][0]==x)ch[y][0]=0,fa[x]=0;} inline void link(int x,int y){makeroot(x),fa[x]=y,splay(x);}}lct;int a[N];inline const int read(){ register int f=1,x=0; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return f*x;}int main(){ int n=read(); lct.sz[n+1]=1; for(register int i=1;i<=n;i++) { a[i]=read(); a[i]=(i+a[i]<=n+1?i+a[i]:n+1); lct.fa[i]=a[i]; lct.sz[i]=1; } int m=read(); while(m--) { int op=read(); if(op==1) { int x=read()+1; lct.makeroot(n+1); lct.access(x),lct.splay(x); printf("%d\n",lct.sz[x]-1); } else { int x=read()+1,y=read(); lct.cut(x,a[x]); a[x]=(x+y<=n+1?x+y:n+1); lct.link(x,a[x]); } } return 0;}/******************** ********************/