[HNOI2010]弹飞绵羊(分块)

题目描述

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

输入输出格式

输入格式：

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1。

接下来一行有n个正整数，依次为那n个装置的初始弹力系数。

第三行有一个正整数m，

接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。

输出格式：

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

2
3

说明

对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

题解

　　这里需要我们处理出每一块中，进入某个点后，会进入下一个块的哪一个点，需要几次才能弹出块，修改时记得同时修改相应块的内容。

　　靠大佬自己思维了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=500001;
int n,m,ch[N],tmp,belong[N],l[N],r[N],num,out[N],sum[N];
int read()
{
    int x=0,w=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return w*x;
}

void build()
{
    num=tmp;if(tmp*tmp<n)num++;

    for(int i=1;i<=num;i++)
    {
        l[i]=num*(i-1)+1;r[i]=num*i;
        
    }
    r[num]=n;

    int s=1 ;
    for (int i=1;i<=n;i++) {if (i>r[s]) s++; belong[i]=s;}
}

void change(int left,int right)
{
    for(int i=right;i>=left;i--)
    {
        if(i+ch[i]>r[belong[i]])sum[i]=1,out[i]=i+ch[i];
        else sum[i]=sum[i+ch[i]]+1,out[i]=out[i+ch[i]];
    }
}

int main()
{
    n=read();tmp=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        ch[i]=read();
    }
    build();
    change(1,n);
    m=read();
    for(int i=1;i<=m;i++)
    {
        int qwq;
        qwq=read();
        if(qwq==1)
        {
            int x;x=read();x++;
            int ans=sum[x],qwq=out[x];
            for(int i=belong[x];i<=tmp&&qwq<=n;i++)
            ans+=sum[qwq],qwq=out[qwq];
            printf("%d
",ans);
        }
        else 
        {
            int x,y;x=read();x++;y=read();ch[x]=y;
            change(l[belong[x]],r[belong[x]]);
        }
    }
    return 0;
}