【LCT】弹飞绵羊

一道看起来不是很裸的题目，但是并不难。

题意： 有n块弹板，每块弹板都有一个弹力强度，将在弹板上的绵羊向右弹动x个单位，然后有两种操作，一种是修改弹板的弹力强度，一种是询某位置弹板需要弹多少下才可以弹飞。

分析：

1. 因为每个弹板有固定的弹力强度，所以每个弹板相当于有唯一的父亲。
2. 而弹板都是向右弹的，所以不会出现环。
3. 弹板可以修改弹力强度，意思是弹板到的位置会发生改变，弹板父亲会发生改变。 综上，建立LCT动态树，处理动态的父子问题 注意： 读入的时候就直接用link操作连边，就可以了。

   Code

#include<bits/stdc++.h>
#define lc c[x][0]
#define rc c[x][1]
using namespace std;
const int N=2e5+12;
int n,m,a[N],siz[N],c[N][2],f[N];
int nroot(int x)
{
  return c[ f[x] ][0]==x || c[f[x]][1]==x;
}
void pushup(int x)
{
  siz[x]=siz[lc]+siz[rc]+1;
}
void rotate(int x)
{
  int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
  if( nroot(y) ) c[z][c[z][1]==y]=x;
  c[x][!k]=y;c[y][k]=w;
  if(w) f[w]=y;
  f[y]=x;f[x]=z;
  pushup(y);
}
void splay(int x)
{
  int y=x,z=0;
    while( nroot(x) )
  {
    y=f[x],z=f[y];
    if( nroot(y) )
      rotate( (c[y][0]==x)^(c[z][0]==y)?x:y );
    rotate(x);
  }
  pushup(x);
}
void access(int x)
{
  for(int y=0;x;x=f[y=x]) splay(x),rc=y,pushup(x);
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)
  { cin>>a[i];
    if(i+a[i]<=n) f[i]=i+a[i];
   }
  cin>>m;
  int o,x,y;
  while(m--)
  {
    cin>>o;
    if(o==1)
    {
      cin>>x;
      x++;
      access(x),splay(x);
      //打通x到目前他的根节点路径，并用splay将x节点的儿子甩开。
      cout<<siz[x]<<endl;
    }
    else
    {
      cin>>x>>y;
      x++;
      access(x);splay(x);
      c[x][0]=f[ c[x][0] ]=0;
      if( x+y<=n ) f[x]=x+y;
      pushup(x);
    }

  }



}