Description
某天，Lostmonkey发明了一种超级弹力装置，为了在 他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当 绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次 后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。
Input
第 一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接 下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成 k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000
Output
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
Sample Input
4 1 2 1 1 3 1 1 2 1 1 1 1
Sample Output
2 3
解题思路：
LCT，很显然要让 i 与 i 能到的点连边，yy一个不存在的点n+1，让所有点与它连边表示弹飞。
更改时先Cut后Link
最后查询时将n+1与x路径提取，查询重量即可（注意要-1^_^）
代码：
1 #include2 #include 3 #include 4 #define lll tr[spc].ch[0] 5 #define rrr tr[spc].ch[1] 6 #define ls ch[0] 7 #define rs ch[1] 8 const int N=300000; 9 struct trnt{ 10 int ch[2]; 11 int lzt; 12 int fa; 13 int wgt; 14 bool anc; 15 }tr[N]; 16 int nx[N]; 17 int n,m; 18 bool whc(int spc) 19 { 20 return tr[tr[spc].fa].rs==spc; 21 } 22 void pushup(int spc) 23 { 24 tr[spc].wgt=tr[lll].wgt+tr[rrr].wgt+1; 25 return ; 26 } 27 void trr(int spc) 28 { 29 if(!spc) 30 return ; 31 std::swap(lll,rrr); 32 tr[spc].lzt^=1; 33 return ; 34 } 35 void pushdown(int spc) 36 { 37 if(tr[spc].lzt) 38 { 39 tr[spc].lzt=0; 40 trr(lll); 41 trr(rrr); 42 } 43 return ; 44 } 45 void recal(int spc) 46 { 47 if(!tr[spc].anc) 48 recal(tr[spc].fa); 49 pushdown(spc); 50 return ; 51 } 52 void rotate(int spc) 53 { 54 int f=tr[spc].fa; 55 bool k=whc(spc); 56 tr[f].ch[k]=tr[spc].ch[!k]; 57 tr[spc].ch[!k]=f; 58 if(tr[f].anc) 59 { 60 tr[spc].anc=1; 61 tr[f].anc=0; 62 }else 63 tr[tr[f].fa].ch[whc(f)]=spc; 64 tr[spc].fa=tr[f].fa; 65 tr[f].fa=spc; 66 tr[tr[f].ch[k]].fa=f; 67 pushup(f); 68 pushup(spc); 69 return ; 70 } 71 void splay(int spc) 72 { 73 recal(spc); 74 while(!tr[spc].anc) 75 { 76 int ft=tr[spc].fa; 77 if(tr[ft].anc) 78 { 79 rotate(spc); 80 return ; 81 } 82 if(whc(spc)^whc(ft)) 83 rotate(spc); 84 else 85 rotate(ft); 86 rotate(spc); 87 } 88 return ; 89 } 90 void access(int spc) 91 { 92 int lst=0; 93 while(spc) 94 { 95 splay(spc); 96 tr[rrr].anc=1; 97 tr[lst].anc=0; 98 rrr=lst; 99 pushup(spc);100 lst=spc;101 spc=tr[spc].fa;102 }103 return ;104 }105 void Mtr(int spc)106 {107 access(spc);108 splay(spc);109 trr(spc);110 return ;111 }112 void Link(int spc,int y)113 {114 access(spc);115 splay(spc);116 tr[spc].fa=y;117 return ;118 }119 void Cut(int x,int y)120 {121 Mtr(x);122 access(y);123 splay(x);124 tr[x].rs=0;125 tr[y].anc=1;126 tr[y].fa=0;127 return ;128 }129 void split(int x,int y)130 {131 Mtr(x);132 access(y);133 splay(y);134 }135 int dest(int i)136 {137 return (i+nx[i]>n)?(n+1):(i+nx[i]);138 }139 int main()140 {141 scanf("%d",&n);142 for(int i=1;i<=n+1;i++)143 tr[i].anc=1;144 for(int i=1;i<=n;i++)145 {146 scanf("%d",&nx[i]);147 Link(i,dest(i));148 }149 scanf("%d",&m);150 while(m--)151 {152 int i,j,k;153 scanf("%d",&i);154 if(i==1)155 {156 scanf("%d",&j);157 j++;158 split(j,n+1);159 printf("%d\n",tr[n+1].wgt-1);160 }else{161 scanf("%d%d",&j,&k);162 j++;163 Cut(j,dest(j));164 nx[j]=k;165 Link(j,dest(j));166 }167 }168 return 0;169 }