BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊 LCT

这道题的lct不想说什么......

这道题是lct的假板子题你需要精简并适当改进LCT给他加上不清真的属性......

#include<cstdio>
#include<cstring>
#define MAXN 200010
using namespace std;
struct spaly
{
   spaly *ch[2],*f;
   int size;
   void pushup()
   {
     size=ch[1]->size+ch[0]->size+1;
   }
}null[MAXN];
int n,m,a[MAXN];
inline int get(spaly *p)
{
   return p->f->ch[1]==p;
}
inline bool isroot(spaly *p)
{
   return p->f->ch[0]!=p&&p->f->ch[1]!=p;
}
inline void rotate(spaly *p)
{
   spaly *fa=p->f,*pa=fa->f;
   int j=get(p);
   if(!isroot(fa))pa->ch[get(fa)]=p;
   if((fa->ch[j]=p->ch[j^1])!=null)fa->ch[j]->f=fa;
   fa->f=p;
   p->f=pa;
   p->ch[j^1]=fa;
   fa->pushup();
   p->pushup();
}
inline void Spaly(spaly *p)
{
   for(spaly *fa=p->f;!isroot(p);rotate(p),fa=p->f)
    if(!isroot(fa))
      rotate(get(fa)==get(p)?fa:p);
}
inline void expose(spaly *p)
{
   spaly *y=null;
   while(p!=null)
   {
     Spaly(p);
     p->ch[1]=y;
     p->pushup();
     y=p;
     p=p->f;
   }
}
inline void link(spaly *x,spaly *y)
{
   Spaly(x);
   x->f=y;
}
inline void cut(spaly *x,spaly *y)
{
   expose(x);
   Spaly(x);
   x->ch[0]->f=null;
   x->ch[0]=null;
   x->pushup();
}
inline void Init()
{
   scanf("%d",&n);
   null->ch[0]=null->ch[1]=null->f=null;
   for(int i=1;i<=n;i++)
    null[i].ch[0]=null[i].ch[1]=null[i].f=null,null[i].size=1;
   for(int i=1;i<=n;i++)
   {
    scanf("%d",&a[i]);
    if(i+a[i]<=n)link(null+i,null+i+a[i]);
   }
}
inline void work()
{
   scanf("%d",&m);
   while(m--)
   {
     int opt;
     scanf("%d",&opt);
     int x,y;
     if(opt==1)
     {
       scanf("%d",&x);
       x++;
       expose(null+x);
       Spaly(null+x);
       printf("%d\n",null[x].size);
     }
     else
     {
       scanf("%d%d",&x,&y);
       x++;
       expose(null+x);
       Spaly(null+x);
       if(null[x].size!=1)cut(null+x,null+x+a[x]);
       a[x]=y;
       if(x+y<=n)link(null+x,null+x+y);
     }
   }
}
int main()
{
  Init();
  work();
  return 0;
}      

转载于:https://www.cnblogs.com/TSHugh/p/7153561.html