bzoj2002

题意：

一条直线上有n个装置，每个装置设定初始弹力系数$k_i$，当达到第i个装置时，它会往后弹$k_i$步，达到第$i+k_i$个装置，若不存在第$i+k_i$个装置，则绵羊被弹飞。

有两种操作：

1 x：当它从第i个装置起步时，被弹几次后会被弹飞。

2 x y：修改第x个弹力装置的弹力系数为y。

思路：

因为直接暴力的话一步一步弹太慢了，是$O(n)$的，可以考虑分块提前把弹几步处理出来，这样就可以把弹的复杂度变成$O(\sqrt n)$。

所以要处理出来每一个装置到下一块的落点和步数。

分为三种情况：

1.下一步直接弹出：pos=-1,step=1；

2.下一步弹到块内：pos=pos[Next[i]],step=step[Next[i]]+1；

3.下一步弹到后面的块内：pos=Next[i],step=1。

对于查询，循环求出步数。

对于修改，因为一个装置的修改会影响到块内装置的信息，所以从后往前更新块内装置的信息即可。

复杂度为$O(m*\sqrt n)$。

代码：

int n;
int num;//分块的个数
int belong[200010];//每个数属于哪个分块
int block;//每个块的大小
int lef[200010],rig[200010];//该块的左/右端点位置
int pos[200010],step[200010];//到下一块的落地位置/最小步数
int Next[200010];
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
    {
        lef[i]=(i-1)*block+1;
        rig[i]=i*block;
    }
    rig[num]=n;//最后一块不满的情况
}
int main()
{
    scanf("%d",&n);
    build();
    for(int i=1;i<=n;i++)
        scanf("%d",&Next[i]);
    for(int i=n;i>=1;i--)
    {
        if(i+Next[i]>n)//直接弹出
        {
            pos[i]=-1;
            step[i]=1;
        }
        else if(i+Next[i]<=rig[belong[i]])//在同一块内
        {
            pos[i]=pos[i+Next[i]];
            step[i]=step[i+Next[i]]+1;
        }
        else//弹出当前块
        {
            pos[i]=i+Next[i];
            step[i]=1;
        }
    }
    int m,op;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d",&op);
        if(op==1)   //查询
        {
            int ans=0,cur;
            scanf("%d",&cur);
            cur++;
            while(cur!=-1)
            {
                ans+=step[cur];
                cur=pos[cur];
            }
            printf("%d\n",ans);
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);//把x装置变为系数变为y
            x++;
            Next[x]=y;
            for(int i=x;i>=lef[belong[x]];i--)
            {
                if(i+Next[i]>n)//直接弹出
                {
                    pos[i]=-1;
                    step[i]=1;
                }
                else if(i+Next[i]<=rig[belong[i]])//在同一块内
                {
                    pos[i]=pos[i+Next[i]];
                    step[i]=step[i+Next[i]]+1;
                }
                else//弹出当前块
                {
                    pos[i]=i+Next[i];
                    step[i]=1;
                }
            }
        }
    }
    return 0;
}

HDU6394

update…