【bzoj 4764】弹飞大爷

Description

自从WC退役以来，大爷是越来越懒惰了。为了帮助他活动筋骨，也是受到了弹飞绵羊一题的启发，机房的小伙伴们决定齐心合力构造一个下面这样的序列。这个序列共有N项，每项都代表了一个小伙伴的力量值，如果大爷落到了第i个小伙伴的手里，那么第i个小伙伴会把大爷弹到第i+ai个小伙伴手里，其中ai就是第i个小伙伴的力量值，也就是序列的第i项。然而，因为大爷太沉了，所以有些小伙伴不能撑到锻（you）炼（xi）结束，所以我们中途会替换一些小伙伴，也就是改变序列的某些项。而且，因为大爷太沉了，所以有些小伙伴不能把大爷扔向前方，而是会把大爷往反方向扔，也就是序列中的一些项会是负的（当然，也可能是零喽）。现在机智的大爷通过在空中的观察，已经知道小伙伴们的所有活动——即初始序列、所有更改操作，他想请你算一算，如果他在某时刻落到了某个位置，那么他会在几次弹起之后落到小伙伴序列之外（毕竟摔在地上还是蛮疼的）。

Input

第一行为两个整数N和M，代表序列长度和操作次数。

第二行为N个整数，代表初始的小伙伴序列。

接下来有M行，每行代表一个操作。

如果这一行的第一个数是1，代表该操作是一个询问操作，接下来一个数X，代表询问此时大爷从X处，经过几次弹起会摔在地上。如果永远不会摔在地上，请输出-1。

如果这一行的第一个数是2，代表该操作是一个更改操作，接下来两个数X，Y，代表将序列的第X项改为Y。

N,M <= 200000 |Ai| < N

Output

对于每次询问操作，输出弹起次数或-1。

Sample Input

3 19
1 1 1
1 1
1 2
1 3
2 1 2
1 1
1 2
1 3
2 3 -1
1 1
1 2
1 3
2 2 233
1 1
1 2
1 3
2 2 -233
1 1
1 2
1 3

Sample Output

3
2
1
2
2
1
-1
-1
-1
3
1
2
3
1
2

调了两天终于A了……万分感谢czl大爷、cyc大爷和yy大爷。

RE了几发之后一直调不出来，心态爆炸开始乱搞，然后就WA了。怪我自己没有理解好写法。

因为有环，所以需要隐藏环上的一条边来使其成为森林，hl数组与hr数组即代表隐藏边的端点。

剩下的直接上代码……

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 int n,m,t,u,v,a[N],hl[N],hr[N],st[N];

 struct node{int fa,c[],s;bool rev;}tr[*N];

 int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 bool isroot(int k){return !k||!tr[k].fa||(tr[tr[k].fa].c[]!=k&&tr[tr[k].fa].c[]!=k);}

 void up(int k){tr[k].s=tr[tr[k].c[]].s+tr[tr[k].c[]].s+;}

 void down(int k)

 {

     int l=tr[k].c[],r=tr[k].c[];

     if(tr[k].rev)

     {

         tr[k].rev^=;tr[l].rev^=;tr[r].rev^=;

         swap(tr[k].c[],tr[k].c[]);

     }

     if(l)hl[l]=hl[k],hr[l]=hr[k];

     if(r)hl[r]=hl[k],hr[r]=hr[k];

 }

 void rotate(int x)

 {

     int y=tr[x].fa,z=tr[y].fa,l,r;

     if(tr[y].c[]==x)l=;else l=;r=l^;

     if(!isroot(y)){if(tr[z].c[]==y)tr[z].c[]=x;else tr[z].c[]=x;}

     tr[x].fa=z;tr[y].fa=x;tr[tr[x].c[r]].fa=y;

     tr[y].c[l]=tr[x].c[r];tr[x].c[r]=y;

     up(y);up(x);

 }

 void splay(int x)

 {

     int top=;st[++top]=x;

     for(int i=x;!isroot(i);i=tr[i].fa)st[++top]=tr[i].fa;

     for(int i=top;i;i--)down(st[i]);

     while(!isroot(x))

     {

         int y=tr[x].fa,z=tr[y].fa;

         if(!isroot(y))

         {

             if((tr[y].c[]==x)^(tr[z].c[]==y))rotate(x);

             else rotate(y);

         }

         rotate(x);

     }

 }

 void acs(int x)

 {

     int t=;

     while(x){splay(x);tr[x].c[]=t;up(x);t=x;x=tr[x].fa;}

 }

 void mkroot(int x){acs(x);splay(x);tr[x].rev^=;}

 int find(int x){acs(x);splay(x);while(tr[x].c[])x=tr[x].c[];return x;}

 void link(int x,int y){mkroot(x);tr[x].fa=y;acs(x);splay(x);}

 void cut(int x,int y)

 {

     mkroot(x);acs(y);splay(y);

     tr[x].fa=tr[y].c[]=;up(y);

     hl[x]=hr[x]=hl[y]=hr[y]=;

 }

 void xlink(int x,int y)

 {

     if(find(x)==find(y))hl[y]=x,hr[y]=y;

     else link(x,y);

 }

 void xcut(int x,int y)

 {

     acs(x);splay(x);int li=hl[x],ri=hr[x];

     if(hl[x]==x&&hr[x]==y)hl[x]=hl[y]=hr[x]=hr[y]=;

     else

     {

         cut(x,y);

         if(li&&ri)xlink(li,ri);//划重点！xlink而不是link。

     }

 }

 int query(int x)

 {

     mkroot(n+);acs(x);splay(x);

     if(hl[x]&&hr[x])return -;

     return tr[x].s-;

 }

 int main()

 {

     n=read();m=read();

     for(int i=;i<=n+;i++)tr[i].s=;

     for(int i=;i<=n;i++)

     {

         a[i]=read();

         if(i+a[i]<=||i+a[i]>n)link(i,n+);

         else xlink(i,i+a[i]);

     }

     while(m--)

     {

         t=read();

         if(t==)u=read(),printf("%d\n",query(u));

         else

         {

             u=read();v=read();

             if(u+a[u]<=||u+a[u]>n)cut(u,n+);

             else xcut(u,u+a[u]);

             if(u+v<=||u+v>n)link(u,n+);

             else xlink(u,u+v);

             a[u]=v;

         }

     }

     return ;

 }

巴特西