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的情况，你都要输出一个需要的步数，占一行。
解法一LCT见【这里】。
分成 n√ 块，对于每个点记录跳几次才能出了自己的块以及跳到哪里，对于询问就从这个点开始跳一遍，对于修改就暴力重算所属块的所有元素，复杂度 O(mn√) 。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int oo=0x3f3f3f3f;
int rd()
{int x=0;char c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x;
}
struct edge
{int u,v,a,b;void read(){u=rd();v=rd();a=rd();b=rd();}bool operator < (const edge &e) const{return a<e.a;}
}g[100010];
int fa[400010],son[400010][2],sta[400010],w[400010],mx[400010],tag[400010],
n,m,ans=oo;
int isroot(int u)
{return son[fa[u]][0]!=u&&son[fa[u]][1]!=u;
}
void up(int u)
{mx[u]=u;if (son[u][0]&&w[mx[son[u][0]]]>w[mx[u]]) mx[u]=mx[son[u][0]];if (son[u][1]&&w[mx[son[u][1]]]>w[mx[u]]) mx[u]=mx[son[u][1]];
}
void down(int u)
{if (tag[u]){if (son[u][0]) tag[son[u][0]]^=1;if (son[u][1]) tag[son[u][1]]^=1;swap(son[u][0],son[u][1]);tag[u]=0;}
}
void rot(int u,int k)
{int v=son[u][k],w=son[v][k^1],p=fa[u];if (!isroot(u)) son[p][son[p][1]==u]=v;fa[v]=p;son[u][k]=w;fa[w]=u;son[v][k^1]=u;fa[u]=v;up(u);up(v);up(p);
}
void splay(int u)
{int top=0,x,y,v,w;for (int i=u;;i=fa[i]){sta[++top]=i;if (isroot(i)) break;}for (;top;top--) down(sta[top]);while (!isroot(u)){v=fa[u];x=son[v][1]==u;if (isroot(v)) rot(v,x);else{w=fa[v];y=son[w][1]==v;if (x==y){rot(w,x);rot(v,x);}else{rot(v,x);rot(w,y);}}}
}
void access(int u)
{int v=0;while (u){splay(u);son[u][1]=v;up(u);v=u;u=fa[u];}
}
void makeroot(int u)
{access(u);splay(u);tag[u]^=1;
}
int find(int u)
{access(u);splay(u);while (son[u][0]) u=son[u][0];return u;
}
void link(int u,int v)
{makeroot(u);fa[u]=v;
}
void cut(int u,int v)
{makeroot(u);access(v);splay(v);son[v][0]=fa[u]=0;up(v);
}
int qry(int u,int v)
{makeroot(u);access(v);splay(v);return mx[v];
}
int main()
{int u;n=rd();m=rd();for (int i=1;i<=m;i++) g[i].read();sort(g+1,g+m+1);for (int i=1;i<=n;i++) mx[i]=i;for (int i=1;i<=m;i++){w[n+i]=g[i].b;mx[n+i]=n+i;if (find(g[i].u)!=find(g[i].v)){link(n+i,g[i].u);link(n+i,g[i].v);}else{u=qry(g[i].u,g[i].v);if (w[u]>w[n+i]){cut(u,g[u-n].u);cut(u,g[u-n].v);link(i+n,g[i].u);link(i+n,g[i].v);}}if (find(1)==find(n)) ans=min(ans,g[i].a+w[qry(1,n)]);}if (ans==oo) printf("-1\n");else printf("%d\n",ans);
}