题目大意
某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
解题思路
直接抅出lct，只需要link和cut还有维护splay的size即可。
code
#include
#include
#include
#include
#define LF double
#define LL long long
#define ULL unsigned long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j,k) for(int i=begin[j][k];i;i=next[j][i])
using namespace std;
int const mn=2*1e5+9,inf=1e9+7;
int n,a[mn],size[mn],fa[mn],par[mn],son[mn][2];
void update(int now){if(!now)return;size[now]=size[son[now][0]]+size[son[now][1]]+1;
}
int side(int now){int tmp=fa[now];return son[tmp][1]==now;
}
void rotate(int now){int tmp=fa[now],tm2=side(now);son[fa[tmp]][side(tmp)]=now;fa[now]=fa[tmp];son[tmp][tm2]=son[now][!tm2];fa[son[now][!tm2]]=tmp;son[now][!tm2]=tmp;fa[tmp]=now;update(tmp);update(now);
}
void splay(int now,int root){while(fa[now]!=root){int tmp=fa[now];if(fa[tmp]!=root){if(side(now)==side(tmp))rotate(tmp);else rotate(now);}rotate(now);}
}
int first(int now){while(son[now][0])now=son[now][0];return now;
}
void indep(int now){splay(now,0);int tmp=son[now][1];if(!tmp)return;tmp=first(tmp);splay(tmp,now);son[now][1]=fa[tmp]=0;par[tmp]=now;update(now);
}
void access(int now){indep(now);while(par[now=first(now)]){splay(now,0);int tmp=par[now];indep(tmp);son[tmp][1]=now;fa[now]=tmp;update(tmp);now=tmp;}
}
int main(){freopen("d.in","r",stdin);freopen("d.out","w",stdout);scanf("%d",&n);fo(i,1,n){scanf("%d",&a[i]);int tmp=min(i+a[i],n+1);par[i]=tmp;size[i]=1;}int q;scanf("%d",&q);fo(cas,1,q){int op;scanf("%d",&op);if(op==1){int x;scanf("%d",&x);x++;access(x);splay(x,0);printf("%d\n",size[x]-1);}else{int x,y;scanf("%d%d",&x,&y);x++;int tmp=min(x+a[x],n+1);access(tmp);a[x]=y;tmp=min(x+a[x],n+1);par[x]=tmp;}}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
