[HNOI2010] 弹飞绵羊 bounce

标签：分块。
题解：

　　200000，而且标号从0开始，很符合分块的条件啊。看看怎么实现。
　　首先分成√n个区间，然后如果我们对于每一个位置i，求出一个Next[i]和step[i]，分别表示跳到的后一个位置与步数，因为是分块所以就是跳到下一个区间的步数与位置了。处理这两个数组要从前到后，只需要O(n)。
　　然后查询：自然是使用这两个数组，跳出去就return，复杂度O(√n)。
　　修改：修改一个点自然是O(1)，但是前面的会跳到这个地方，那不是前面的都要改？非也，因为Next[]仅仅跨越了一个区间，所有最多有这个区间的起始位置到i个是需要更改的，也就是最大√n个，我们从i到起始位置烦着枚举，复杂度O(√n)。
　　所以总的复杂度为O(m√n)。

 #include<cmath>

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 int n,m,cnt;

 int W[MAXN],Next[MAXN],step[MAXN],team[MAXN];

 inline int gi(){int res; scanf("%d",&res); return res;}

 void update(int p)

 {

   if(p+W[p]>=n)

     {

       step[p]=;

       Next[p]=n;

       return ;

     }

   int net=p+W[p];

   if(team[p]==team[net])

     {

       step[p]=step[net]+;

       Next[p]=Next[net];

     }

   else

     {

       step[p]=;

       Next[p]=net;

     }

 }

 int query(int p)

 {

   int res=;

   while(p!=n)

     {

       res+=step[p];

       p=Next[p];

     }

   return res;

 }

 int main()

 {

   n=gi(); cnt=sqrt(n);

   for(int i=;i<n;i++) W[i]=gi();

   for(int i=;i<n;i++) team[i]=i/cnt;

   for(int i=n-;i>=;i--) update(i);

   m=gi();

   while(m--)

     {

       int op=gi(),p=gi();

       if(op==)

         {

           int w=gi();

           W[p]=w;

           for(int i=p;i>=;i--)

             if(team[p]==team[i])

               update(i);

             else

               break;

         }

       else

         printf("%d\n",query(p));

     }

   return ;

 }

标签：LCT
题解：

　　此题当然不缺乏LCT做法，对于LCT来说，这道题就是一道模板题，每次修改cut再link，维护sz代表子树的大小。使用一个根节点：n+1，也就是跳出去。M+A+S，查询x的左子树大小即可，也就是比他深度小的点的个数，不就是多少步跳出去吗？

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 int n,m;

 int fa[MAXN],rev[MAXN],val[MAXN],Q[MAXN],ch[MAXN][],sz[MAXN];

 bool isroot(int x){ return ch[fa[x]][]!=x && ch[fa[x]][]!=x; }

 void Update(int x){ sz[x]=sz[ch[x][]]+sz[ch[x][]]+; }

 bool get(int x){ return ch[fa[x]][]==x ;}

 void Down(int x){ if(rev[x]){ rev[ch[x][]]^=; rev[ch[x][]]^=; rev[x]^=; swap(ch[x][],ch[x][]); } }

 void Rotate(int x)

 {

   int old=fa[x],oldf=fa[old],op=get(x);

   if(!isroot(old)) ch[oldf][ch[oldf][]==old]=x;

   ch[old][op]=ch[x][op^]; fa[ch[x][op^]]=old;

   ch[x][op^]=old; fa[old]=x; fa[x]=oldf;

   Update(old); Update(x);

 }

 void Splay(int x)

 {

   int tp=; Q[]=x;

   for(int i=x;!isroot(i);i=fa[i]) Q[++tp]=fa[i];

   for(int i=tp;i;i--) Down(Q[i]);

   for(int FA; !isroot(x) ; Rotate(x))

     {

       FA=fa[x];

       if(!isroot(FA)) Rotate(get(x)==get(FA)?FA:x);

     }

 }

 void Access(int x){ int t=; while(x){ Splay(x); ch[x][]=t; Update(x); t=x; x=fa[x]; } }

 void Makeroot(int x){ Access(x); Splay(x); rev[x]^=;}

 void Link(int x,int y){ Makeroot(x); fa[x]=y;}

 void Cut(int x,int y){ Makeroot(x); Access(y); Splay(y); if(ch[y][]==x) fa[x]=ch[y][]=;}

 int main( )

 {

   scanf("%d",&n); sz[n+]=;

   for(int i=;i<=n;i++) scanf("%d",&val[i]) , sz[i]=;

   for(int i=n;i>=;i--) Link(i,min(i+val[i],n+));

   scanf("%d",&m);

   while(m--)

     {

       int x,op,y,ans=;

       scanf("%d%d",&op,&x); x++;

       if(op==)

         {

           Makeroot(n+); Access(x); Splay(x);

           printf("%d\n",sz[ch[x][]]);

         }

       else

         {

           scanf("%d",&y);

           Makeroot(n+); Access(x);

           Cut(x,min(x+val[x],n+));

           val[x]=y;

           Link(x,min(x+val[x],n+));

         }

     }

   return ;

 }

巴特西

[HNOI2010] 弹飞绵羊 bounce

最新文章

热门文章