BZOJ2002 弹飞绵羊

这题可以用分块暴力做，这里给出正解LCT的代码。

对于每一个弹射器i+k相当于i的父亲，大于n的全部归到n+1上。

这样对于修改操作就像于换了个父亲，我们要记录下上一次的父亲因为在splay中父亲可能会改变。

对于查询操作就相当于把n+1mroot到根，因为你添加时会更新，不能确保n+1的位置。

而答案就是xsplay到根后左儿子的大小，因为你access操作是带着当前splay中比他浅的点一起上去的（一开始这里没有想明白）

具体实现看代码吧

By：大奕哥

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=2e5+5;
  4 int size[N],c[N][2],rev[N],fa[N],nex[N],n,m;
  5 bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
  6 void pushdown(int x)
  7 {
  8     if(rev[x])
  9     {
 10         rev[c[x][0]]^=1;rev[c[x][1]]^=1;rev[x]^=1;
 11         swap(c[x][0],c[x][1]);
 12     }
 13     return;
 14 }
 15 void update(int x)
 16 {
 17     size[x]=size[c[x][0]]+size[c[x][1]]+1;
 18     return;
 19 }
 20 void rotate(int x)
 21 {
 22     int y=fa[x],z=fa[y],l,r;
 23     l=c[y][1]==x;r=l^1;
 24     if(!isroot(y))c[z][c[z][1]==y]=x;
 25     fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
 26     c[y][l]=c[x][r];c[x][r]=y;
 27     update(y);update(x);
 28     return;
 29 }
 30 int s[N];
 31 void splay(int x)
 32 {
 33     int top=0;int i;
 34     for(i=x;!isroot(i);i=fa[i])s[++top]=i;s[++top]=i;
 35     for(int i=top;i;--i)pushdown(s[i]);
 36     while(!isroot(x))
 37     {
 38         int y=fa[x],z=fa[y];
 39         if(!isroot(y))
 40         {
 41             if(c[y][0]==x^c[z][0]==y)rotate(x);
 42             rotate(y);
 43         }
 44         rotate(x);
 45     }
 46     return;
 47 }
 48 void access(int x)
 49 {
 50     int y=0;
 51     while(x)
 52     {
 53         splay(x);
 54         c[x][1]=y;
 55         y=x;x=fa[x];
 56     }
 57     return;
 58 }
 59 void mroot(int x)
 60 {
 61     access(x);splay(x);rev[x]^=1;
 62 }
 63 void link(int x,int y)
 64 {
 65     mroot(x);fa[x]=y;splay(x);
 66 }
 67 void cut(int x,int y)
 68 {
 69     mroot(x);access(y);splay(y);c[y][0]=fa[x]=0;
 70 }
 71 int main()
 72 {
 73     scanf("%d",&n);int x,y,f;
 74     for(int i=1;i<=n;++i)
 75     {
 76         scanf("%d",&x);
 77         fa[i]=x+i;size[i]=1;
 78         if(fa[i]>n)fa[i]=n+1;
 79         nex[i]=fa[i];
 80     }
 81     size[n+1]=1;
 82     scanf("%d",&m);
 83     for(int i=1;i<=m;++i)
 84     {
 85         scanf("%d",&f);
 86         if(f==1)
 87         {
 88             mroot(n+1);
 89             scanf("%d",&x);x++;
 90             splay(x);int ans1=0;
 91             ans1+=size[c[x][0]];
 92             access(x);splay(x);
 93             printf("%d
",ans1+size[c[x][0]]);
 94         }
 95         else
 96         {
 97             scanf("%d%d",&x,&y);
 98             x++;y=min(n+1,x+y);
 99             cut(x,nex[x]);link(x,y);nex[x]=y;
100         }
101     }
102     return 0;
103 }