标签 - 差分

? 解题记录 ? ? 洛谷 ? ? 树链剖分 ? ? 差分 ?    2018-10-09 14:25:45    380    0    0
小C同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。 这个游戏的地图可以看作一棵包含  个结点和  条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从  到  的连续正整数。 现在有  个玩家,第  个玩家的起点为 ,终点为 。每天打卡任务开始时,所有玩家在第  秒同时从自己的起点出发,以每秒跑一条边的速度,不间断地沿着最
? 解题记录 ? ? 树链剖分 ? ? 差分 ?    2018-04-04 19:01:19    437    0    0
题目描述松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的。天哪,他居然真的住在”树“上。 松鼠想邀请小熊维尼前来参观,并且还指定一份参观指南,他希望维尼能够按照他的指南顺序,先去a1,再去a2,......,最后到an,去参观新家。可是这样会导致维尼重复走很多房间,懒惰的维尼不停地推辞。可是松鼠告诉他,每走到一个房间,他就可以从房间拿一块糖果吃。 维尼是个馋家伙,立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃,他需要在每一个房间各放至少多少个糖果。 因为松鼠参观指南上的最后一个房间an是餐厅,餐厅里他准
? 解题记录 ? ? 洛谷 ? ? 差分 ?    2017-11-23 11:19:37    577    0    0
题目描述To meet the ever-growing demands of his N (1 <= N <= 50,000) cows, Farmer John has bought them a new soda machine. He wants to figure out the perfect place to install the machine. The field in which the cows graze can be represented as a one-dimensional number line. Cow i grazes in
? 解题记录 ? ? 洛谷 ? ? 树状数组 ? ? 差分 ? ? 模板 ?    2017-09-09 21:08:49    855    0    0
题目描述如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数数加上x 2.求出某一个数的和 输入输出格式输入格式:   第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。 第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。 接下来M行每行包含2或4个整数,表示一个操作,具体如下: 操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k 操作2: 格式:2 x 含义:输出第x个数的值   输出格式:   输出包含若干行整数,即为所有操作2的结果。   输入输出样例输入样例#1:5 5
? 解题记录 ? ? 洛谷 ? ? 二分答案 ? ? 差分 ?    2017-08-21 08:58:30    622    0    0
题目背景公元 2044 年,人类进入了宇宙纪元。 题目描述L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。 小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物 流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。 为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。 在虫洞的