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
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
2
3
3
HINT
Source
强行用分块做，算是另一种分块的用法，分块真奇妙啊。
受到了来自abclzr的细心教导，首先思考最普通的模拟，发现可以O(n)路径压缩，O(1)的查询，但是需要修改就变成了O（n^2）的修改，于是考虑分块，记录一下每个点跳出该点所在的块的步数，也就是在每块内进行路径压缩，还有记录每个点跳出块后到达的点，同样可以块内路径压缩完成，这样就变成了O(sqrt(n))的修改和查询，但是预处理是O(n*sqrt(n))的，虽然可以过，但是LCT更快啦啦，我偏要写分块啦啦,读入优化背了一晚上WA的锅啦啦啦MD。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define N 200010
using namespace std;
int pos[N],st[N],nx[N],k[N];
int n,m,q,block;
inline int read ()
{
char c;
int ans=;
while ((c=getchar())=='\n' || c==' ' || c=='\r');
ans=c-'';
while (isdigit(c=getchar())) ans=ans*+c-'';
return ans;
}
int solve(int x)
{
int ans=;
while ()
{
ans+=st[x];
if (!nx[x]) return ans;
x=nx[x];
}
}
int main()
{
n=read();
block=(int)(sqrt(n));
for (int i=;i<=n;i++)
{
pos[i]=(i-)/block+;
k[i]=read();
}
for (int i=n;i>=;i--)
{
if (i+k[i]>n) st[i]=;
else if (pos[i]==pos[i+k[i]])
{
st[i]=st[i+k[i]]+;
nx[i]=nx[i+k[i]];
}
else
{
st[i]=;
nx[i]=i+k[i];
}
}
q=read();
for (int i=;i<=q;i++)
{
int x,y,z;
x=read();y=read();
y++;
if (x==) printf("%d\n",solve(y));
else
{
z=read();
k[y]=z;
for (int j=y;j>=(pos[y]-)*block+;j--)
{
if (j+k[j]>n) st[j]=,nx[j]=;
else if (pos[j]==pos[j+k[j]])
{
st[j]=st[j+k[j]]+;
nx[j]=nx[j+k[j]];
}
else
{
st[j]=;
nx[j]=j+k[j];
}
}
}
}
return ;
}
2016.3.24 学LCT，这果然是模板题。。。
#include <iostream>
#include <cstdio>
#define N 200020
using namespace std;
int n,m;
struct SplayNode
{
SplayNode *fa,*ch[];
int step;
bool chr() {return this==fa->ch[];}
bool check() {return this!=fa->ch[] && this !=fa->ch[];}
void updata() {step=ch[]->step+ch[]->step+;}
}*lct[N],*null;
inline int read() {int ans=; char c; while ((c=getchar())>'' || c<''); ans=c-''; while (isdigit(c=getchar())) ans=ans*+c-''; return ans;}
inline void MakeTree(SplayNode *x) {x->fa=x->ch[]=x->ch[]=null; x->step=;}
void init() {null=new SplayNode; null->fa=null->ch[]=null->ch[]=null; null->step=;}
inline void rotate(SplayNode *x)
{
SplayNode *r=x->fa;
int t=x->chr();
if (!r->check()) r->fa->ch[r->chr()]=x;
x->fa=r->fa;
r->ch[t]=x->ch[t^];
r->ch[t]->fa=r;
r->fa=x;
x->ch[t^]=r;
r->updata();
}
inline void splay(SplayNode *x)
{
for (;!x->check();rotate(x))
if (!x->fa->check())
if (x->chr()==x->fa->chr()) rotate(x->fa);
else rotate(x);
x->updata();
}
inline SplayNode *access(SplayNode *x)
{
SplayNode *y=null;
for (;x!=null;y=x,x=x->fa)
{
splay(x);
x->ch[]=y;
}
return y;
}
inline void link(SplayNode *x,SplayNode *y)
{
access(x); splay(x);
x->ch[]->fa=null; x->ch[]=null; x->fa=y; x->updata();
}
int main()
{
init();
n=read();
for (int i=;i<n;i++)
{
lct[i]=new SplayNode;
MakeTree(lct[i]);
}
for (int i=;i<n;i++)
{
int x;
x=read();
if (i+x<n) lct[i]->fa=lct[i+x];
}
m=read();
for (int i=;i<=m;i++)
{
int temp,x,y;
temp=read(); x=read();
if (temp==)
{
access(lct[x]);
splay(lct[x]);
printf("%d\n",lct[x]->step);
}
else
{
y=read();
if (x+y<n) link(lct[x],lct[x+y]);
else link(lct[x],null);
}
}
return ;
}
LCT