某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
这是一道比较明显的动态树问题，初始时将 i 和i k[i]连起来，当要求修改 x 节点的弹力时，先将原来的边(i,i k[i])断开，然后修正 k[i] 连接，因为要考虑弹飞的问题，所以我们设置 n+1 节点表示被弹飞，所以前面的 i+k[i] 都要和 n+1 取 min 。
#include<cstdio> #include<algorithm> using namespace std; const int maxn=200005; struct jz{ int s,son[2],f,flg; }a[maxn]; int n,Q,k[maxn],top,stack[maxn]; inline int _read(){ int num=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') num=num*10+ch-48,ch=getchar(); return num; } void pushup(int x){a[x].s=a[a[x].son[0]].s+a[a[x].son[1]].s+1;} void tag(int x){swap(a[x].son[0],a[x].son[1]);a[x].flg^=1;} void pushdown(int x){ if (!a[x].flg) return; if (a[x].son[1]) tag(a[x].son[1]); if (a[x].son[0]) tag(a[x].son[0]); a[x].flg=0; } bool is_ro(int x){return x!=a[a[x].f].son[1]&&x!=a[a[x].f].son[0];} void rotate(int x){ int fa=a[x].f,d=x==a[fa].son[0]; if (!is_ro(fa)) a[a[fa].f].son[fa==a[a[fa].f].son[1]]=x; a[fa].son[d^1]=a[x].son[d];a[a[x].son[d]].f=fa;a[x].son[d]=fa; pushup(fa);pushup(x);a[x].f=a[fa].f;a[fa].f=x; } void splay(int x){ stack[++top]=x; for (int i=x;!is_ro(i);i=a[i].f) stack[++top]=a[i].f; while (top) pushdown(stack[top--]); while (!is_ro(x)){ int fa=a[x].f; if (!is_ro(fa)){ int d1=fa==a[a[fa].f].son[1],d2=x==a[fa].son[1]; if (d1==d2) rotate(fa);else rotate(x); } rotate(x); } } void Access(int x){ int lst=0; while(x){ splay(x);a[x].son[1]=lst;pushup(x); lst=x;x=a[x].f; } } void make_ro(int x){Access(x);splay(x);tag(x);} void link(int x,int y){make_ro(y);a[y].f=x;} void cut(int x,int y){ make_ro(y);Access(x);splay(x); a[y].f=a[x].son[0]=0;pushup(x); } int main(){ freopen("exam.in","r",stdin); freopen("exam.out","w",stdout); n=_read(); for (int i=1;i<=n+1;i++) a[i].s=1; for (int i=1;i<=n;i++) k[i]=_read(),link(min(i+k[i],n+1),i); Q=_read(); while (Q--){ int d=_read(),x=_read()+1,y; if (d==1){ make_ro(n+1);Access(x);splay(x); printf("%d\n",a[x].s-1); }else cut(min(x+k[x],n+1),x),link(min(x+(k[x]=_read()),n+1),x); } return 0; }