标签:线段树

5.1 B

huangkui 2018年5月1日 No Comments Problem ,

Description 有一个 N 块石头组成的蓄水池,第 i 块石头高度为 ai。 你需要进行两种操作: 1.询问蓄水池的容量(蓄水池最多能储存多少水)。 2.将第 x 块石头的高度增加 v。

Luogu P3224 [HNOI2012]永无乡(线段树合并)

huangkui 2018年2月19日 No Comments Problem , , , , ,

题目链接:传送门 Description 永无乡包含 n 座岛,编号从 1 到 n,每座岛都有自己的独一无二的重要度,按照重要度可 以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座(含 0 座)桥可以到达岛 b,则称岛 a 和岛 b 是连 通的。 现在有两种操作: B x y 表示在岛 x 与岛 y 之间修建一座新桥。 Q x k 表示询问当前与岛 x连通的 […]

Luogu P3722 [AH2017/HNOI2017]影魔(暴力+扫描线+线段树)

huangkui 2018年2月13日 No Comments Problem , , ,

题目链接:传送门 Description 大意:给你一个N的排列,对于区间[l,r],若l和r为区间最大值与次大值,则对区间有p1的贡献;若l和r中一个位最大值,一个不为次大值,则有p2的贡献。有m个查询[l,r],查询区间[l,r]内的贡献

Luogu P2468 [SDOI2010]粟粟的书架(主席树+二分答案)

huangkui 2018年2月11日 No Comments Problem , , , , , , , ,

题目链接:传送门 Description 幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友,她的爱好是画画和读书,尤其喜欢Thomas H. Cormen的文章。粟粟家中有一个R行C列的巨型书架,书架的每一个位置都摆有一本书,上数第i行、左数第j列摆放的书有Pi,j页厚。 粟粟每天除了读书之外,还有一件必不可少的工作就是摘苹果,她每天必须摘取一个指定的苹果。粟粟家果树上的苹果有的高、有的低,但无论如何凭粟粟自己的个头都难以摘到。不过她发现 […]

Luogu P3168 [CQOI2015]任务查询系统(主席树)

huangkui 2018年2月11日 No Comments Problem , , , ,

题目链接:传送门 Description 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束(第Si秒和Ei秒任务也在运行),其优先级为Pi。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第Xi秒正在运行的任务中,优先级最小的Ki个任务(即将任务按照优 […]

Luogu P3313 [SDOI2014]旅行(树剖)

huangkui 2018年2月10日 No Comments Problem , , ,

题目链接:传送门 Description S国有N个城市,编号从1到N。城市间用N-1条双向道路连接,满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教,如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。 为了方便,我们用不同的正整数代表各种宗教, S国的居民常常旅行。旅行时他们总会走最短路,并且为了避免麻烦,只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级,旅行者们常会记下 […]

Luogu T21778 过年(权值线段树+扫描线思想)

huangkui 2018年2月9日 No Comments Problem , , , , ,

题目链接:传送门 Description 有 n(1 \\leq n \\leq 10^5)个小朋友,过年了,要发放 m(1 \\leq m \\leq 10^5)次礼物。 每次发放,会给出三个参数 l,r,k(1 \\leq l \\leq r \\leq n, 1 \\leq k \\leq 10^5),表示给区间[l,r] 内的小朋友都发一个礼物k。 所有礼物发放完成后,对于每一个小朋友,回答他接受的礼物中,出现次数最多的礼物是什么。如果有 […]

Page 1 of 2