标签: 线段树

5 篇文章

BZOJ3166 [HEOI2013]ALO
题面 Welcome to ALO ( Arithmetic and Logistic Online)。这是一个 VR MMORPG, 如名字所见,到处充满了数学的谜题 现在你拥有 n 颗宝石,每颗宝石有一个能量密度,记为 ai,这些宝石的能量 密度两两不同。现在你可以选取连续的一些宝石(必须多于一个)进行融合,设 为 ai, ai+1, …, a…
BZOJ3248 [ioi2013]robots
题目描述 $Marita$ 的弟弟把玩具扔在客厅地板上,乱七八糟。庆幸的是,$Marita$ 设计了一种特殊的机器人可以收拾玩具。 不过,她需要确定哪个机器人去拣起哪个玩具。 一共有$T$个玩具,整数$W[i]$表示这个玩具的重量,整数$S[i]$表示这个玩具的体积。机器人有两种,分别是:弱机器人和小机器人。 有 $A$ 个弱机…
BZOJ2957 楼房重建(线段树维护单调上升序列)
题面   小A的楼房外有一大片施工工地,工地上有N栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。  为了简化问题,我们考虑这些事件发生在一个二维平面上。小A在平面上$(0,0)$点的位置,第i栋楼房可以用一条连接$(i,0)$和$(i,Hi)$的线段表示,其中$Hi$为第$i$栋楼房的高…
BZOJ3545 Peaks
题目 在$Bytemountains$有N座山峰,每座山峰有他的高度$h_i$。有些山峰之间有双向道路相连,共$M$条路径,每条路径有一个困难值,这个值越大表示越难走,现在有$Q$组询问,每组询问询问从点v开始只经过困难值小于等于$x$的路径所能到达的山峰中第$k$高的山峰,如果无解输出$-1$。 思路 首先打开题解$kruskal重构树$+$主席…
LOJ白金元首与克劳德斯
题面 思路 本题偏向思维吧,需要注意一点,开始时所有云都是没有重叠面积且速度相同的,所以往同一方向的云都是相对静止的,并且云的速度方向只有向右和向上,这样就给了我们一个十分优秀的性质--只有向上与向右的云才会重叠,并且最多一个位置只能被两朵云覆盖,最少一朵云,所以只需要判断任意一朵的向右的云是否将会与向上的相交即可,设向右的云有$n$朵,向上的云有…