UFPE Starters Final Try-Outs 2019 Recife, Brazil, Dec 1, 2018 Problem J(线段树+二分)
链接
题目大意:现在有n个房子,从1到n从左向右排列。每个房子有一个高度,一个人要向通过这个房子,他的高度必须和房子的高度完全相等。你可以修改一个人的身高,给定你一个D,你能使一个人的身高最多增加D或最多减少D。
现在给定你次询问。询问类型1,将一个指定房子的高度修改成其他值。询问类型2,若一个人从一个房子出发,你的修改身高能力的上限为D(每通过一个房子可以修改一次),那么这个人在最远在哪个房子停下来?
房子的高度没什么用,真正有用的是相邻房子的高度差值。因此我们可以搞个绝对值差分数组存储相邻房子的高度差。然后我们可以直接暴力。而这里暴力会超时。我们可以观察,如果此人在第i个房子开始,到第j个...
more...