当前位置: 首页 > 编程日记 > 正文

[HNOI 2010]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

题解

首先,建立一个虚拟节点$n+1$,绵羊到达这个节点即被弹飞。

对于每个装置,

如果$i+K_i<=n$,则执行$Link(i,i+K_i)$,否则$Link(i,n+1)$。

对于修改操作,先执行$Cut(j,j+K_j)$(如果$j+K_j>n$则为$n+1$),再执行$Link(j,j+k)$(如果$j+k>n$则为$n+1$),

并把$K_j$赋为$k$。

对于询问操作,分别执行$MakeRoot(n+1)$,$MakeRoot(x)$,最终答案即为$size[x]-1$。

其中$size[i]$表示平衡树中节点$i$的子树的大小。

  1 //It is made by Awson on 2017.12.24
  2 #include <map>
  3 #include <set>
  4 #include <cmath>
  5 #include <ctime>
  6 #include <queue>
  7 #include <stack>
  8 #include <vector>
  9 #include <cstdio>
 10 #include <string>
 11 #include <cstdlib>
 12 #include <cstring>
 13 #include <iostream>
 14 #include <algorithm>
 15 #define LL long long
 16 #define Max(a, b) ((a) > (b) ? (a) : (b))
 17 #define Min(a, b) ((a) < (b) ? (a) : (b))
 18 using namespace std;
 19 const int N = 200000;
 20 
 21 int n, m, k[N+5], opt, a, b;
 22 struct Link_Cut_Tree {
 23     int ch[N+5][2], pre[N+5], size[N+5], isrt[N+5], rev[N+5];
 24     Link_Cut_Tree () {
 25     memset(isrt, 1, sizeof(isrt));
 26     }
 27     void pushup(int o) {
 28     if (!o) return;
 29     size[o] = size[ch[o][0]]+size[ch[o][1]]+1;
 30     }
 31     void pushdown(int o) {
 32     if (!o || !rev[o]) return;
 33     int ls = ch[o][0], rs = ch[o][1];
 34     swap(ch[ls][0], ch[ls][1]), swap(ch[rs][0], ch[rs][1]);
 35     rev[ls] ^= 1, rev[rs] ^= 1, rev[o] = 0;
 36     }
 37     void push(int o) {
 38     if (!isrt[o]) push(pre[o]);
 39     pushdown(o);
 40     }
 41     void rotate(int o, int kind) {
 42     int p = pre[o];
 43     ch[p][!kind] = ch[o][kind], pre[ch[o][kind]] = p;
 44     if (isrt[p]) isrt[o] = 1, isrt[p] = 0;
 45     else ch[pre[p]][ch[pre[p]][1] == p] = o;
 46     pre[o] = pre[p];
 47     ch[o][kind] = p, pre[p] = o;
 48     pushup(ch[o][kind]), pushup(o);
 49     }
 50     void splay(int o) {
 51     push(o);
 52     while (!isrt[o]) {
 53         if (isrt[pre[o]]) rotate(o, ch[pre[o]][0] == o);
 54         else {
 55         int p = pre[o], kind = ch[pre[p]][0] == p;
 56         if (ch[p][kind] == o) rotate(o, !kind), rotate(o, kind);
 57         else rotate(p, kind), rotate(o, kind);
 58         }
 59     }
 60     }
 61     void access(int o) {
 62     int y = 0;
 63     while (o) {
 64         splay(o); size[o] -= size[ch[o][1]];
 65         isrt[ch[o][1]] = 1, isrt[ch[o][1] = y] = 0;
 66         o = pre[y = o];
 67         pushup(o);
 68     }
 69     }
 70     void makeroot(int o) {
 71     access(o), splay(o);
 72     rev[o] ^= 1, swap(ch[o][0], ch[o][1]);
 73     }
 74     void link(int x, int y) {
 75     makeroot(x); pre[x] = y;
 76     }
 77     void cut(int x, int y) {
 78     makeroot(x), access(y), splay(y);
 79     size[y] -= size[x];
 80     ch[y][0] = pre[x] = 0, isrt[x] = 1;
 81     }
 82     int query(int x) {
 83     makeroot(n+1), makeroot(x);
 84     return size[x]-1;
 85     }
 86 }T;
 87 
 88 void work() {
 89     scanf("%d", &n);
 90     for (int i = 1; i <= n; i++) T.size[i] = 1;
 91     for (int i = 1; i <= n; i++) {
 92     scanf("%d", &k[i]);
 93     T.link(i, Min(k[i]+i, n+1));
 94     }
 95     scanf("%d", &m);
 96     while (m--) {
 97     scanf("%d", &opt);
 98     if (opt == 1) {
 99         scanf("%d", &a); a++;
100         printf("%d\n", T.query(a));
101     }else {
102         scanf("%d%d", &a, &b); a++;
103         T.cut(a, Min(k[a]+a, n+1));
104         k[a] = b;
105         T.link(a, Min(k[a]+a, n+1));
106     }
107     }
108 }
109 int main() {
110     work();
111     return 0;
112 }

转载于:https://www.cnblogs.com/NaVi-Awson/p/8097444.html

相关文章:

WordPress首页调用QQ签名

我的博客&#xff1a;http://Yourtion.TK 看到我的博客的朋友一定注意到我的页面旁边一个QQ签名的实时显示&#xff0c;如下图&#xff1a; 是怎么实现的呢&#xff1f;&#xff1f;下面一步步告诉你。希望对你有帮助。 首先登陆QQ滔滔首页&#xff1a;http://www.taotao.com/并…

断网,启用网络,关机的实现。

windows 下实现 shutdown_two.c 此为第三版 // 我需要一个断开网络&#xff0c;启用网络&#xff0c;定时发送邮件后关机的功能&#xff0c;其中定时发送邮件功能是邮件客户端完成&#xff1b;原来的工具是用bat实现的&#xff0c;后来给BAT内容放到C中&#xff0c;延时部分用…

BaseTDI.sys 瑞星卡巴冲突,导致机器蓝屏

今天中午在给本次评教活动导入各学院10级学生信息时&#xff0c;多次出现蓝屏&#xff0c;其主要错误信息为 “BaseTDI.SYS Address 9188783F base at 91887000 Data Stamp 45a47636”.并且 提示“crash dump …..&#xff08;系统崩溃&#xff09;”. 于是&#xff0c…

【22,23节】Django的GET和POST属性笔记

COOKIES&#xff1a;一个标准的python字典对象&#xff0c;包含所有cookies&#xff0c;键和值都为字符串session&#xff1a;一个即能读又能写的类似字典对象&#xff0c;表示当前的会话&#xff0c;只有当django启用会话的支持时才可用 一键多值的GET[]只能接收到最后一个值&…

dataTable 表格组件刷新 问题记录

1 、 重绘 使用fnDraw() 进行刷新表格使用的前体是开启了服务端分页和查询时使用此进行刷新表格 fnDraw(boolean)true : 表示整体刷新 且刷新后 到起始页 false &#xff1a; 刷新后在刷新前的页 2、 $(#confess-table-info).DataTable().ajax.reload()重绘 使用此方法进行…

旺铺免费,淘宝的义务不能免

旺铺免费&#xff0c;淘宝的义务不能免阿祥春节前夕&#xff0c;淘宝网免费开放“旺铺扶持版”&#xff0c;降低创业门槛&#xff0c;希望帮助更多中小卖家快速成长。从大道理上讲&#xff0c;旺铺免费&#xff0c;是淘宝所承担的社会责任&#xff0c;既为政府分忧&#xff0c;…

下载安装 binary editor

http://www.eecanalyzer.net/downloads 转载于:https://www.cnblogs.com/sea-stream/p/10842190.html

使用Mpvue 使用 scroll-view 记录以及 页面设置弹窗后 页面滚动问题

1、scroll-view 使用 <scroll-view scroll-y"true"class"msg-list"scrolltolower"scrolltolower"scroll"scroll"> </scroll-view> methods: {scrolltolower(){console.log(7)},scroll(e) {console.log(6)console.log(e…

YOLOv10环境搭建、模型预测和ONNX推理

运行后会在文件yolov10s.pt存放路径下生成一个的yolov10s.onnxONNX模型文件。安装完成之后,我们简单执行下推理命令测试下效果,默认读取。终端,进入base环境,创建新环境。(1)onnx模型转换。

时间不同单位之间的转换

在观察仿真波形的时候&#xff0c;经常会出现微妙&#xff0c;毫秒&#xff0c;皮秒之间的转换&#xff0c;出现过错误&#xff0c;每次记不清楚的时候还要重新查资料&#xff0c;现总结如下. 秒&#xff08;second&#xff09;是国际单位制中时间的基本单位&#xff0c;符号是…

关于Javascript的内存泄漏问题的整理稿

常规循环引用内存泄漏和Closure内存泄漏 要了解javascript的内存泄漏问题&#xff0c;首先要了解的就是javascript的GC原理。 我记得原来在犀牛书《JavaScript: The Definitive Guide》中看到过&#xff0c;IE使用的GC算法是计数器&#xff0c;因此只碰到循环 引用就会造成mem…

C#计算两个日期的相隔天数

DateTime start Convert.ToDateTime(dateStart.ToShortDateString()); DateTime end Convert.ToDateTime(dateEnd.ToShortDateString()); TimeSpan sp end.Subtract(start); int days sp.Days;转载于:https://www.cnblogs.com/weimingxin/p/8109234.html

.NET 端口监听

1.直接调用微软socket对象处理 static void Main(string[] args){try{IPAddress ip new IPAddress(new byte[] { 127, 0, 0, 1 });//在3721端口新建一个TcpListener对象TcpListener listener new TcpListener(ip, 3721); listener.Start();Console.WriteLine("started l…

微信小程序导航栏设置透明

使用的时Mpvue 在app.json 文件中设置 "window": {"navigationStyle": "custom"},

epub 电子书软件代码销售

epub 电子书软件代码销售本套代码用来读取epub 格式电子书。主要面向&#xff1a;有一定开发能力的人员&#xff0c;和有一定制作水平的朋友们。用途&#xff1a;自己开发学习&#xff0c;钻研&#xff0c;出appstore 应用&#xff0c;卖钱&#xff0c;加广告赚钱等。&#xff…

重新编译iptables

重新编译iptables一&#xff0e;重新编译后的内核版本为&#xff1a;<?xml:namespace prefix st1 ns "urn:schemas-microsoft-com:office:smarttags" />2.6.28.10重新编译后的iptables的版本为&#xff1a;1.4.4&#xff0c;新添加了layer7的模块&#xff0…

爬虫之Xpath详解

爬虫之Xpath详解 XPath介绍 XPath 是一门在 XML 文档中查找信息的语言。XPath 可用来在 XML 文档中对元素和属性进行遍历。 XPath 是 W3C XSLT 标准的主要元素&#xff0c;并且 XQuery 和 XPointer 都构建于 XPath 表达之上。 因此&#xff0c;对 XPath 的理解是很多高级 XML 应…

非常认同的《SEO优化大全》

1、每个网页标题简洁&#xff0c;不超过30字。  2、每个网页核心关键词不超过3个。如果可以&#xff0c;你要学会放弃。  3、最重要的关键词放在标题首位&#xff0c;依次类推。  4、网站的描述&#xff0c;简洁&#xff0c;明了&#xff0c;最开始和结束部分自然出现关键…

python中tornado的第一个例子

python中tornado的第一个例子 1 先安装tornado pip install tornado 2 新建tor.py 记住不能建立 tornado.py 这样的名字 不然会报错 ImportError: No module named tornado.ioloop; tornado is not a package import tornado.ioloop import tornado.webclass MainHandler(tor…

docker 安装和使用

目录 1、安装docker的官方网站 配置镜像加速器 查看docker安装的版本 重启docker 启动 docker 查看启动的状态 下载测试镜像 并且启动该容器 2、操作docker 镜像的常用命令 搜索镜像 下载镜像 列出镜像 删除本地镜像 保存镜像到本地 加载镜像到docker仓库 构…

不编译内核加载connlimit模块

转载于:https://blog.51cto.com/sookk8/280372

记录一下g++的编译选项

假设main.cpp,hello.h,hello.cpp,其中main.cpp调用了hello类中的方法 1 生成hello.so g -shared hello.cpp -olibhello.so 2 编译main.cpp,并链接,并指定运行时libhello.so的位置 g main.cpp -lhello -L./ -Wl,-rpath./ -o main 值得一提的是,如果采用带版本号的库,例如libhell…

JSP中是EL表达式与JSTL

EL语法&#xff1a;${ } EL取值来自于作用域对象 1.如何从指定作用域取值(默认从最小作用域取值)   pageScope、requestScope、sessionScope、applicationScope   ${pageScope.xxx }--- ${requestScope.xxx} --- ${sessionScope.xxx } 2.用EL取出请求参数中的数据   EL表…

数据库连接无法释放

问题已解决,发现是数据库连接无法释放,不知道是什么原因,同样的代码在本地就是好的,在服务器端就有问题,最后在连接串里加入以下语句解决问题. Poolingtrue; MAX Pool Size512;Min Pool Size50;Connection Lifetime30 转载于:https://www.cnblogs.com/tianciliangen/p/8110625.…

mpvue 引入自己创建的js 文件 到其他的文件中

1、mpvue 引入外部js 文件 中的方法 如果需要调用外部的js文件中的方法 需要按照以下的格式进行写 创建方法&#xff0c;将方法抛出 /** * 七牛上传文件 工具方法 **/ function getToken() {console.info("进来了"); } export {getToken }在其他的文件中使用 im…

DirectShow camera demo

我在编译SDK自带的Cameracapture的例子时&#xff0c;出现 生成: 0 已成功, 1 已失败, 0 最新, 0 已跳过 1> ------ 已启动生成: 项目: CameraCapture, 配置: Release Windows Mobile 5.0 Pocket PC SDK (ARMV4I) ------ 1> 正在链接... 1> graphmanager.obj : …

Uva 11400 - Lighting System Design (DP)

题目链接 https://cn.vjudge.net/problem/UVA-11400【题意】你的任务是设计一个照明系统&#xff0c;一共有n&#xff08;n<1000&#xff09;个灯泡可以选择&#xff0c;不同种类的灯必须使用不同的电源&#xff0c;但同种灯泡可以共用一个电源&#xff0c;每种灯泡有4个属性…

删除表中多余的重复记录,重复记录是根据单个字段(peopleId)来判断,只留有rowid最小的记录...

delete from people where rowid in (select min(rowid) from people group by peopleId having count(peopleId )>1)转载于:https://www.cnblogs.com/macT/p/10865224.html

微信表白墙 微信小程序 吐槽墙 表白墙 java 开发

目录 1 小程序展示 2 后台展示 3 技术栈 4 代码目录 5 第一版微信表白墙链接 1 小程序展示 2 后台展示 3 技术栈 java:Springboot mybatis mysql mpvue bootstrap dataTable echars 4 代码目录 5 第一版微信表白墙链接 https://blog.csdn.net/huyande123/article/det…

Sql存储过程加密和解密

可用于加密SQL存储过程或者触发器&#xff08;这是SQL Server本身提供的&#xff0c;也就是说这是微软的加密算法&#xff09; http://www.mscto.com 使用 WITH ENCRYPTION 选项 WITH ENCRYPTION 子句对用户隐藏存储过程的文本。下例创建加密过程&#xff0c;使用 sp_helptext …