当前位置: 首页 > news >正文

P4511 日程管理

题目大意:

你现在有 \(n\) 个任务,每个任务有 \(t_{i},p_{i}\),表示你如果能在前 \(t_{i}\) 天做完这个任务,那么你会有 \(p_{i}\) 的收益,每个任务都要恰好做一天。
任务是善变的,一开始没有任何任务,你要维护 \(q\) 次操作,每次操作删除或添加一个任务,每次修改后问答案。
\(n,t \le 3 \times 10^5\)

解题思路:

对于一组任务,能同时完成他们当且仅当 \(\forall_{t} t \ge \sum [t_{i} \le t]\)
考虑这个过程直接维护并不好维护,所以我们考虑加入/删除一个任务的可能的变化。
由于这个题类似后缀减,所以所选的任务最多有 \(O(1)\) 变化。

拿两个线段树维护,一个里面放 multiset,为了记录当前所选的任务的 \(p\) 最小值。
另一个表示 \(t - \sum[a_{i} \le t]\),为了检查要修改哪个。

\(O(n \log^2 n)\)

为什么总是想不到维护修改量呢?
直接不好去维护那就去想想修改量吧。

http://www.jsqmd.com/news/36992/

相关文章:

  • 11.10学习总结
  • 新编故事 | 噪音
  • Oracle数据库实例深度解析与实践指南
  • 2025 年 11 月流量计厂家推荐排行榜,热式/模拟式/数字式/高压/高温/耐腐蚀/多气体/4-20mA/RS485/分体式/不锈钢/高精度流量计公司推荐
  • 20232405 2024-2025-1 《网络与系统攻防技术》实验四实验报告
  • 2025 年 11 月聚氨酯厂家推荐排行榜,浇注型聚氨酯,聚氨酯预聚体,聚氨酯胶黏剂,聚氨酯组合料,聚氨酯密封,聚氨酯轮,聚氨酯胶辊,聚氨酯制品公司推荐
  • duckdb比sqlite大多了
  • 20232303 2025-2026-1 《网络与系统攻防技术》实验四实验报告
  • 2025 年 11 月氢氧化镁厂家推荐排行榜,矿石氢氧化镁,矿石法氢氧化镁,水镁石氢氧化镁,阻燃剂氢氧化镁,改性氢氧化镁公司推荐
  • 20232415 2025-2026-1 《网络与系统攻防技术》实验四实验报告
  • React:使用Tailwind CSS、Streamdown与Ant Design X
  • Day17清除默认样式
  • 2025 年 11 月磨粉机厂家推荐排行榜,雷蒙磨粉机,环辊磨粉机,摆式磨粉机,矿石磨粉机,超细磨粉机,高压磨粉机公司推荐
  • 详细介绍:探究微波消解仪如何创新现代实验室的样品前处理流程
  • 爆肝!Oracle RAC 日常运维命令总结
  • Python 面向对象编程进阶
  • 详细介绍:线性代数 几何意义 | 基础、向量、行列式与线性方程组(上篇)
  • Emacs Org-Mode插入文本内容,自动对齐表格(Org-Babel)
  • 在Zabbix中修改Web页面显示名称
  • 2025 年 11 月润滑油厂家推荐排行榜,工业润滑油,汽车润滑油,发动机润滑油,甲醇发动机润滑油,全合成润滑油公司精选
  • 2025 年 11 月护栏生产厂家推荐排行榜,锌钢护栏,市政护栏,道路护栏,阳台护栏,草坪护栏公司推荐
  • python中Flask框架下session的使用
  • 20232406 2025-2026-1 《网络与系统攻防技术》实验四实验报告
  • 软件工程学习日志2025.11.10
  • 172. 阶乘后的零
  • 2025 年 11 月储罐厂家推荐排行榜,钢衬塑储罐,钢塑复合储罐,化工储罐,防腐储罐,PE储罐,盐酸储罐,硫酸储罐,聚丙烯储罐,不锈钢储罐,次氯酸钠储罐公司推荐
  • AWS云从业者认证学习指南与练习平台
  • 微服务已死?别再盲目跟风微服务!这3种情况下单体架构更适合你。
  • Oracle LogMiner实战指南:误删误改数据的救命稻草
  • Spring 事务 - 实践