CF 13E Holes （块状链表）

题目大意：

有N个洞，每个洞有相应的弹力，能把这个球弹   i+power【i】 位置去。

有两个操作，

0 a b 把a位置的弹力改成b

1 a 在a处放一个球，要你输出他能弹多少次，最后一次落在哪个洞。

块状链表 是用数组作为节点的链表，但是链表又可以用数组实现。所以我们要记录的是

block[i]  表示[i]这个位置属于第几个块

每一个洞在这个块中跳到的最尾位置，也就是end[x]

每一个洞要在这个块中跳多少次。也就是cnt[x]

每一个洞的在这个块中最后会跳到那里，但是如果这个洞已经是这个块的最后位置  那么就要到下一个块。也就是next[x]

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 100005
using namespace std;

int block[maxn],cnt[maxn],end[maxn],next[maxn];
int save[maxn];
int BLOCK;
int n,m;

void make(int x)
{
    int y=x+save[x];
    if(y>n)//如果已经出界
    {//这还是很好理解的   出口就是自己  next就弄成边界   
        end[x]=x;
        next[x]=n+1;
        cnt[x]=1;
    }
    else
    {
        if(block[x]==block[y])//如果下一个跟自己是一个块区。那么我们就要找他最后面一个
        {
            next[x]=next[y];
            end[x]=end[y];
            cnt[x]=cnt[y]+1;
        }
        else//否则就去下个块区找
        {
            next[x]=y;
            cnt[x]=1;
            end[x]=x;
        }
    }
}


void query(int x)
{
    int c=cnt[x],e=end[x];
    while(1)
    {
        x=next[x];
        if(x>n)break;
        c+=cnt[x];
        e=end[x];
    }
    printf("%d %d\n",e,c);
}
int main()
{
    scanf("%d%d",&n,&m);
    BLOCK=(int)ceil(sqrt(1.0*n));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&save[i]);
        block[i]=i/BLOCK;
    }

    for(int i=n;i;i--)make(i);//从后面往前面处理

    int op;
    while(m--)
    {
        scanf("%d",&op);
        int a,b;
        if(op)
        {
            scanf("%d",&a);
            query(a);
        }
        else
        {
            scanf("%d%d",&a,&b);
            save[a]=b;
            for(int i=a;i&&block[i]==block[a];i--)make(i);
        }
    }
    return 0;
}

CF 13E Holes （块状链表）,布布扣,bubuko.com

CF 13E Holes （块状链表）

原文：http://blog.csdn.net/u010709592/article/details/21045123