bzoj 2002 [Hnoi2010]Bounce 弹飞绵羊 [分块][特殊处理]_bounce tv shous-程序员宅基地

技术标签: 分块  特殊处理  bzoj  

[Hnoi2010]Bounce 弹飞绵羊

Description

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

Input

第一行包含一个整数n,表示地上有n个装置,装置的编号从0到n-1,接下来一行有n个正整数,依次为那n个装置的初始弹力系数。第三行有一个正整数m,接下来m行每行至少有两个数i、j,若i=1,你要输出从j出发被弹几次后被弹飞,若i=2则还会再输入一个正整数k,表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000,对于100%的数据n<=200000,m<=100000

Output

对于每个i=1的情况,你都要输出一个需要的步数,占一行。
Sample Input
4
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
2
3

[题目思路]
这道题分块很巧妙,,,维护每个点跳出当前分块所需要的步数,和跳出当前分块后所能达到下一个分块的位置。这样就可以提高速度了。具体操作见代码,,并且修改单点是,需要修改的只有这个点所在块的起点到这个点的的st和pos..
修改是倒着修改哦。。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200050;
int block,l[450],r[450],ki[N];
int belong[N],st[N],pos[N];//跳到下一个分块所需步数,下一个分块的位置
int n,m;
inline int readin(){
    int res=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
   if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res*f;
}
int cal(int x){
    int sum=0;
    while(1){
        sum+=st[x];
        x=pos[x];
        if(!x)break;//飞出去了
    }
    return sum;
}
int main(){
    freopen("bzoj.in","r",stdin);
    freopen("bzoj.out","w",stdout);
    n=readin();
    for(int i = 1; i <= n; i++)
        ki[i]=readin();
    int x=sqrt(n);
    if(n%x)block=n/x+1;
    else block=n/x;
    for(int i = 1; i<= block; i++)
        l[i]=(i-1)*x+1,r[i]=min(i*x,n);
    for(int i = 1; i <= n; i++)
        belong[i]=(i-1)/x+1;
    for(int i = n; i>=1; i--){
        if(i+ki[i]>n)st[i]=1;
        else if(belong[i]==belong[i+ki[i]])st[i]=st[i+ki[i]]+1,pos[i]=pos[i+ki[i]];//同属一个分块
        else st[i]=1,pos[i]=i+ki[i];//一步就跳出当前分块
    }
    m=readin();
    for(int i = 1; i <=m; i++){
        int flag=readin(),x=readin()+1;
        if(flag==1)printf("%d\n",cal(x));
        else {
            int y=readin();
            ki[x]=y;
            for(int j=x; j >=l[belong[x]]; j--){
   //只会影响x所在区间
                if(belong[j]==belong[j+ki[j]])
                    st[j]=st[j+ki[j]]+1,pos[j]=pos[j+ki[j]];
                else st[j]=1,pos[j]=j+ki[j];
            }
        }
    }
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lfrun/article/details/52959163

智能推荐

第五节,损失函数:MSE和交叉熵-程序员宅基地

文章浏览阅读424次。损失函数用于描述模型预测值与真实值的差距大小,一般有两种比较常见的算法——均值平方差(MSE)和交叉熵。1、均值平方差(MSE):指参数估计值与参数真实值之差平方的期望值。在神经网络计算时,预测值要与真实值控制在同样的数据分布内,假设将预测值经过Sigmoid激活函数得到取值范围在0~1之间,那么真实值也归一化到0~1之间。2、交叉熵:预测输入样本属于某一类的概率。..._loss mse和交叉熵

win7 + centos7 双系统启动_centos7 windows 同时启动-程序员宅基地

文章浏览阅读1.2w次,点赞5次,收藏16次。本文介绍的是在已有windows系统(默认安装在C盘)基础上安装centos7,设置双系统启动。难点: 1、linux安装程序无法识别NTFS,windows系统无法读写ext3 2、U盘启动盘无法放入大于4G的文件 3、Gurb2 添加启动项分区准备1、下载分区助手,从原有分区中切割分区并删除分区作为安装linux的空间 2、因为linux安装程序无法识别NTFS,U盘启动盘(FAT32格_centos7 windows 同时启动

HTML文档模板 | html/template-程序员宅基地

文章浏览阅读1.7k次。import "html/template"概述索引示例概观模板包(html/template)实现了数据驱动的模板,以便在代码注入过程中安全地生成HTML输出。它提供了与包文本/模板相同的接口,只要输出是HTML,就应该使用它来代替文本/模板。这里的文档侧重于包的安全特性。有关如何自行编写模板的信息,请参阅文本/模板的文档。介绍该软件包包装文本/模板,以便您可以共享其模板API以安全地解析和执行..._html template

FastReport教程:如何在报表中使用多个数据库_fastreport 数据源-程序员宅基地

文章浏览阅读2.6k次。下载FastReport.Net最新版本有时,我们必须以不同的格式处理来自不同来源的数据。对于分析师和报表开发人员来说,这可能是一个令人头疼的问题。毕竟,你必须以某种方式组合数据。幸运的是,在FastReport.Net的报表中,您可以创建许多数据连接。而且,数据源可以完全不同 - 文本文件,数据库。多亏了这一点,我们将能够在一份报表中整合数据。 在本文中,我们将介绍在报表中创建两个数据源以及..._fastreport 数据源

学术海报Poster-- 模板分享_学术海报poster模板下载-程序员宅基地

文章浏览阅读4.4k次,点赞18次,收藏13次。读研期间,发表的论文被录用,一般会通过口述演讲或者Poster海报的形式向参与者展示你的论文科研成果,其中受众面积最大的一般是Poster海报分享的形式。对于论文录用者来说,它也是最简单的一种参会形式,而拥有一份精美的海报模板,对于广大的研究生来说,能省时省力不少,科研工作成果好很重要,但是,用精美的海报展示您的科研成果,让更多的读者了解到你的科研内容/成果,同样也非常重要。我在读研期间,就苦于寻找一份精美的海报模板而花费大量时间,现将这100份模板海报分享给你,希望对你的科研之路也能有一些帮助_学术海报poster模板下载

The k-th Largest Group POJ - 2985 treap+并查集_newman likes playing with cats. he possesses lots -程序员宅基地

文章浏览阅读306次。Newman likes playing with cats. He possesses lots of cats in his home. Because the number of cats is really huge, Newman wants to group some of the cats. To do that, he first offers a number to each o_newman likes playing with cats. he possesses lots of cats in his

随便推点

部署Dashboard,监控应用-程序员宅基地

文章浏览阅读81次。部署web UI(dashboard)用于监控node资源参见文档:https://blog.csdn.net/networken/article/details/85607593官网:https://kubernetes.io/docs/tasks/access-application-cluster/web-ui-dashboard/github:https://github....

避免出现bitmap内存限制OUT OF MEMORY的一种方法-程序员宅基地

文章浏览阅读261次。在编写Android程序的时候,我们总是难免会碰到OOM(OUT OF MEMORY)的错误,那么这个错误究竟是怎么来的呢,可以先看一下这篇文章ANDROID BITMAP内存限制OOM,OUT OF MEMORY。 这里,我使用Gallery来举例,在模拟器中,不会出现OOM错误,但是,一旦把程序运行到真机里,图片文件一多,必然会出现OOM,我们通过做一些额外的处理来避免。1.创建一..._取消限制outofmemory限制

Bailian2966 时区转换【时区计算】-程序员宅基地

文章浏览阅读399次。2966:时区转换总时间限制: 1000ms 内存限制: 65536kB描述直到19世纪,时间校准是一个纯粹的地方现象。每一个村庄当太阳升到最高点的时候把他们的时钟调到中午12点。一个钟表制造商人家或者村里主表的时间被认为是官方时间,市民们把自家的钟表和这个时间对齐。每周一些热心的市民会带着时间标准的表,游走大街小巷为其他市民对表。在城市之间旅游的话,在到达新地方的时候需要把怀表校准。但是,..._2966

android之SharedPreferes_在android中sharedpreferences的文件可以跨类读取吗-程序员宅基地

文章浏览阅读710次。SharedPreferences是Android平台上一个轻量级的存储类,主要是保存一些常用的配置比如窗口状态,一般在Activity中 重载窗口状态onSaveInstanceState保存一般使用SharedPreferences完成,它提供了Android平台常规的Long长 整形、Int整形、String字符串型的保存,它是什么样的处理方式呢?SharedPreferences类似过去W_在android中sharedpreferences的文件可以跨类读取吗

win7和linux(centos)双系统安装成win7单系统_centoslinux能改win7系统吗?-程序员宅基地

文章浏览阅读453次。首先说明一下环境:安装了win7旗舰版和centos双系统。现在的需求是删除linux系统,然后只剩下win7系统,之后再把win7重新安装。步骤:1,先使用大白菜制作一个u盘启动工具,并放入下载好的win7系统镜像2,在win7的磁盘管理(计算机右键->管理->磁盘管理)3,在磁盘管理中删除linux的分区4,重新启动系统,这时有些系统就不能进入win7了5,_centoslinux能改win7系统吗?

layout_gravity和gravity的作用和区别(上)-程序员宅基地

文章浏览阅读2k次,点赞6次,收藏7次。layout_gravity和gravity的作用和区别(上)问题描述: 最近在学习Android布局时需要将位于LinearLayout布局中的控件放在布局底部,这时会使用到android:layout_gravity=“bottom”,但是发现这样是行不通的,最后查资料找出原因,防止忘记在这记一下。gravity: 是对view控件本身来说的,是用来设置view本身的内容应该显示在vi..._layout_gravity