标签:树

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。 所有礼物发放完成后,对于每一个小朋友,回答他接受的礼物中,出现次数最多的礼物是什么。如果有 […]

Luogu P2596 [ZJOI2006]书架(Splay)

huangkui 2018年1月12日 No Comments Problem , , ,

题目链接:传送门 Description 小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一本。由于这些书太有吸引力了,所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的,所以每次放书的时候至少能够将那本书放在拿出来时的位置附近,比如说她拿的时候这本书上面有X本书,那么放回去时这本书上面就只可能有 […]

Page 1 of 2