题解 CF13E 【Holes】

· · 题解

这道题首先看数据范围，10^5,那首先想到分块维护吧，但这道题的分块与普通的分块不太一样，它是一种叫做块状链表的东西维护的。块状链表是什么呢？ （其实就是用链表吧块与块之间连了起来）

那我们要用块状链表维护什么呢？

显而易见，维护每一个点跳出这个块以后会跳在哪里以及所需时间，这样我们一个点只会跳一次，就把一次询问时间复杂度就是O(\sqrt{n})。

那么对于修改操作呢？因为一次修改只会改变一个块里的信息，所以我们需要从右向左的维护，可以实现O(1),为什么要从右向左呢？因为从右向左你可以发现你只需要向右跳一次就可以更新答案，如果你向右跳一步还在块内，因为你向右跳过的点以及更新过了，所以直接继承，如果在块外，那么直接更新。所以修改的时间复杂度也是O(\sqrt{n})的。

修改代码

void change(int x,int y)//x为位置，y为值
{
    int tmp=x,cnt=0;
    a[x]=y;
    while (pos[tmp].k==pos[x].k)tmp+=a[tmp],cnt++;
    pos[x].next=tmp;
    pos[x].w=cnt;
    for (int i=x-1;i>=l[pos[x].k];i--)
    {
        int tmp=i,cnt=0;
        tmp=tmp+a[tmp];//向右跳一步
        if (pos[tmp].k==pos[i].k)//在块内直接继承
        {
            pos[i].next=pos[tmp].next;
            pos[i].w=pos[tmp].w+1;
        }
        else//在块外
        {
            pos[i].next=tmp;
            pos[i].w=1;
        }
    }
}

完整代码

#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=2e5+10;
int n,m,a[maxn],k,l[maxn];
struct node{
    int next,w,k;
}pos[maxn*2];
void ask(int x)
{
    int tmp=x,ans=0,cnt=tmp;
    while(pos[tmp].k)
    {
        ans+=pos[tmp].w;
        cnt=tmp;
        tmp=pos[tmp].next;
    }
    tmp=cnt;
    while(pos[tmp].k==pos[cnt].k)cnt=tmp,tmp+=a[tmp];
    printf("%d %d\n",cnt,ans);
}
void change(int x,int y)
{
    int tmp=x,cnt=0;
    a[x]=y;
    while (pos[tmp].k==pos[x].k)tmp+=a[tmp],cnt++;
    pos[x].next=tmp;
    pos[x].w=cnt;
    for (int i=x-1;i>=l[pos[x].k];i--)
    {
        int tmp=i,cnt=0;
        tmp=tmp+a[tmp];
        if (pos[tmp].k==pos[i].k)
        {
            pos[i].next=pos[tmp].next;
            pos[i].w=pos[tmp].w+1;
        }
        else
        {
            pos[i].next=tmp;
            pos[i].w=1;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)scanf("%d",&a[i]);
    k=sqrt(n);
    for (int i=1;i<=n;i++)pos[i].k=(i-1)/k+1;   
    for (int i=1;i<=n;i++)if (pos[i].k!=pos[i-1].k)l[pos[i].k]=i;
    for (int i=1;i<=n;i++)
    {
        int tmp=i,cnt=0;
        while (pos[tmp].k==pos[i].k)tmp+=a[tmp],cnt++;
        pos[i].next=tmp;
        pos[i].w=cnt;
    }
    for (int i=1;i<=m;i++)
    {
        int opt,x,y;
        scanf("%d",&opt);
        if (opt==1)
        {
            scanf("%d",&x);
            ask(x);
        }
        else
        {
            scanf("%d%d",&x,&y);
            change(x,y);
        }
    }
    return 0;
}