当前位置: 首页 > 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.rkmt.cn/news/45926.html

相关文章:

  • 新编故事 | 噪音
  • 20232303 2025-2026-1 《网络与系统攻防技术》实验四实验报告
  • 2025 年 11 月润滑油厂家推荐排行榜,工业润滑油,汽车润滑油,发动机润滑油,甲醇发动机润滑油,全合成润滑油公司精选
  • 172. 阶乘后的零
  • 微服务已死?别再盲目跟风微服务!这3种情况下单体架构更适合你。
  • Oracle LogMiner实战指南:误删误改数据的救命稻草
  • Spring 事务 - 实践
  • Spring AI Alibaba 项目源码学习(二)-Graph 定义与描述分析
  • 20232422 2024-2025-1 《网络与系统攻防技术》实验四实验报告
  • SPI 设备与多从机冲突的解决之道:片选管理、CS 去抖与总线隔离策略 - 实践
  • pythontip 字符串转为字典
  • JavaWeb04-JUnit
  • 哪款学习机适合小学生用?2025年11月多款主流品牌告诉你如何选
  • AIGC系统
  • [GESP202303 二级] 百鸡问题
  • P11362 [NOIP2024] 遗失的赋值 题解
  • CF 2070F Friends and Pizza
  • 上菱空调维修热线电话-24小时全国统一报修
  • 102302139 尚子骐 数据采集与融合作业2
  • 深入解析:Redis技术应用
  • HTTP 的方法和状态码 - 指南
  • 华凌燃气灶维修全国各售后号码《今日汇总》
  • P12504 「ROI 2025 Day1」树上的青蛙
  • 目前广州往返珠海网约车软件
  • 利用RFM模型对客户进行分类
  • 第三十七篇
  • 华帝热水器维修售后电话24小时—全国各区定点服务中心
  • 基于浏览器的DOCX文件编辑器:实现导入、编辑与导出功能 - 实践
  • 20251110 - KMP
  • 2025年11月智能洗碗机型号推荐榜:麦浪5000plus+领衔全维度对比