【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=2002
【题意】
给定n个数的序列，i可以跳到i+k[i]，需要能够修改k并可以查询跳出n需要的步数。
【思路】
把i->i+k看作一条边，则问题抽象为一个森林，越靠后的点离原树的根越近。
考虑LCT维护大小siz。
修改k的操作可以看作是断边与连边的操作。注意如果直接跳出n应该与null相连以切断原来的边。
一次查询可以先Access使u到根的路径独立，然后splay将u调整至根查询siz。
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; const int N = 4e5+; namespace LCT { struct Node {
Node *ch[],*fa;
int siz;
Node();
void maintain() {
siz=ch[]->siz+ch[]->siz+;
}
} *null=new Node,T[N];
Node::Node() { fa=ch[]=ch[]=null; siz=; }
void rot(Node* o,int d) {
Node *p=o->fa;
p->ch[d]=o->ch[d^];
o->ch[d^]->fa=p;
o->ch[d^]=p;
o->fa=p->fa;
if(p->fa->ch[]==p)
p->fa->ch[]=o;
else if(p->fa->ch[]==p)
p->fa->ch[]=o;
p->fa=o;
p->maintain();
}
void splay(Node* o) {
Node *nf,*nff;
while(o->fa->ch[]==o||o->fa->ch[]==o) {
nf=o->fa,nff=nf->fa;
if(o==nf->ch[]) {
if(nf==nff->ch[]) rot(nf,);
rot(o,);
} else {
if(nf==nff->ch[]) rot(nf,);
rot(o,);
}
}
o->maintain();
}
void Access(Node* o) {
Node *son=null;
while(o!=null) {
splay(o);
o->ch[]=son;
o->maintain();
son=o; o=o->fa;
}
}
void Link(Node* u,Node* v) {
Access(u); splay(u);
u->ch[]->fa=null;
u->ch[]=null;
u->fa=v;
u->maintain();
} }
using namespace LCT; int n,m; int main()
{
null->fa=null->ch[]=null->ch[]=null;
null->siz=;
scanf("%d",&n);
int op,x,y;
for(int i=;i<=n;i++) {
scanf("%d",&x);
if(i+x<=n) T[i].fa=&T[i+x];
}
scanf("%d",&m);
for(int i=;i<=m;i++) {
scanf("%d%d",&op,&x);
x++;
if(op==) {
Access(&T[x]); splay(&T[x]);
printf("%d\n",T[x].siz);
} else {
scanf("%d",&y);
if(x+y<=n) Link(&T[x],&T[x+y]);
else Link(&T[x],null);
}
}
return ;
}