[BZOJ3932/Luogu3168][CQOI2015]任务查询系统(主席树,差分,离散化)

发布于 2018-01-27  9 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3932/Luogu3168][CQOI2015]任务查询系统(主席树,差分,离散化)

Description

最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束(第Si秒和Ei秒任务也在运行),其优先级为Pi。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第Xi秒正在运行的任务中,优先级最小的Ki个任务(即将任务按照优先级从小到大排序后取前Ki个)的优先级之和是多少。特别的,如果Ki大于第Xi秒正在运行的任务总数,则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数,时间的范围在1到n之间(包含1和n)。

Http

BZOJ
Luogu

Tag

主席树,差分,离散化

解决思路

我们考虑对于一个任务\(s->e\),考虑差分在\(s\)加入,在\(t+1\)减去。为了维护区间第\(K\)的相关问题,用主席树维护前缀和即可。
注意离散化

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3932/Luogu3168][CQOI2015]任务查询系统(主席树,差分,离散化)


HNCJ OIer 一枚