数据结构

教主的魔法

题目描述

教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1、2、……、N。 每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W。(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)个英雄的身高) CYZ、光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C,以验证教主的魔法是否真的有效。 WD巨懒,于是他把这个回答的任务交给了你。 (更多…)

DefFrancis
数据结构

[CTSC2008]网络管理

题目描述

M公司是一个非常庞大的跨国公司,在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作,公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器,部门局域网内的所有机器都联向这个路由器,然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。 高速光缆的数据传输速度非常快,以至于利用光缆传输的延迟时间可以忽略。但是由于路由器老化,在这些路由器上进行数据交换会带来很大的延迟。而两个路由器之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的交换延迟时间有关。作为M公司网络部门的一名实习员工,现在要求你编写一个简单的程序来监视公司的网络状况。该程序能够随时更新网络状况的变化信息(路由器数据交换延迟时间的变化),并且根据询问给出两个路由器通信路径上延迟第k大的路由器的延迟时间。 (更多…)

DefFrancis
数据结构

高级打字机

题目描述

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧。 请为这种高级打字机设计一个程序,支持如下3种操作: 1.T x:在文章末尾打下一个小写字母x。(type操作) 2.U x:撤销最后的x次修改操作。(Undo操作) (注意Query操作并不算修改操作) 3.Q x:询问当前文章中第x个字母并输出。(Query操作) 文章一开始可以视为空串。 (更多…)

DefFrancis
数据结构

【模板】可持久化数组(可持久化线段树/平衡树)

题目描述

如题,你需要维护这样的一个长度为 N 的数组,支持如下几种操作
  1. 在某个历史版本上修改某一个位置上的值
  2. 访问某个历史版本上的某一位置的值
此外,每进行一次操作(对于操作2,即为生成一个完全一样的版本,不作任何改动),就会生成一个新的版本。版本编号即为当前操作的编号(从1开始编号,版本0表示初始状态数组) (更多…)

DefFrancis
数据结构

【模板】可持久化平衡树

题目描述

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作(对于各个以往的历史版本):
  1. 插入x数
  2. 删除x数(若有多个相同的数,因只删除一个,如果没有请忽略该操作)
  3. 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x,且最大的数,如不存在输出-2147483647)
  6. 求x的后继(后继定义为大于x,且最小的数,如不存在输出2147483647)
和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本。(操作3, 4, 5, 6即保持原版本无变化) 每个版本的编号即为操作的序号(版本0即为初始状态,空树) (更多…)

DefFrancis
数据结构

XOR的艺术

题目描述

AKN觉得第一题太水了,不屑于写第一题,所以他又玩起了新的游戏。在游戏中,他发现,这个游戏的伤害计算有一个规律,规律如下 1、 拥有一个伤害串为长度为n的01串。 2、 给定一个范围[l,r],伤害为伤害串的这个范围内中1的个数 3、 会被随机修改伤害串中的数值,修改的方法是把[l,r]中的所有数xor上1 AKN想知道一些时刻的伤害,请你帮助他求出这个伤害 (更多…)

DefFrancis