尧图网站建设 尧图网络
  • 首页
  • 关于我们
  • 服务项目
  • 案例展示
  • 建站流程
  • 资讯中心
  • 联系我们
首页/资讯中心/详情

P4511 日程管理

P4511 日程管理
📅 发布时间:2026/6/19 8:16:50

题目大意:

你现在有 \(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)\)。

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

相关新闻

  • 新编故事 | 噪音
  • 20232303 2025-2026-1 《网络与系统攻防技术》实验四实验报告
  • 2025 年 11 月润滑油厂家推荐排行榜,工业润滑油,汽车润滑油,发动机润滑油,甲醇发动机润滑油,全合成润滑油公司精选

最新新闻

  • 从物理模型到代码:一阶与二阶RC滤波器的离散化推导与实践
  • 图纸上的“//”是什么意思?
  • 大模型隐私计算与数据安全技术深度解析:从差分隐私到机器遗忘的全栈隐私保护方案
  • 2026淮南黄金回收白银回收铂金回收门店+工商公安双备案+中检认证商家推荐 - 诚金汇钻回收公司
  • 揭秘XOutput:让老旧游戏手柄在PC游戏中完美工作的终极解决方案
  • 2026兰州黄金回收白银回收铂金回收门店实测|本地正规实体老店无套路门店推荐 - 中安检金银铂钻回收

日新闻

  • 5分钟掌握Python进化算法:Geatpy高性能优化工具完全指南
  • Microchip 24AA044 EEPROM选型与应用全指南:从参数解析到实战编程
  • 华为的鸿蒙到底有多牛?为什么称作遥遥领先?

周新闻

  • 3步解锁iOS设备:applera1n激活锁绕过完全指南
  • 39 2026 人工智能证书终极盘点,普通人选 AI 证书可以从这些方向入手
  • Redis 暴露公网有多危险?从端口检查到补救步骤

月新闻

  • 【总结】入门篇:50句话让你记住架构核心概念
  • WeChatMsg技术方案解析:实现Mac微信数据自主管理的完整解决方案
  • WeChatMsg:革新性微信数据备份方案,打造你的专属数字记忆库

关于尧图

  • 公司简介
  • 团队介绍
  • 企业文化
  • 荣誉资质

服务项目

  • 定制开发
  • 电商建站
  • UI 设计
  • 运维服务

快速链接

  • 案例展示
  • 建站流程
  • 常见问题
  • 资讯中心

联系方式

  • 📍北京市朝阳区互联网产业园 A 座 10 层
  • 📞400-888-8888
  • ✉️contact@rkmt.cn
  • 🕐周一至周日 9:00-21:00

© 2024 北京尧图网络科技有限公司 版权所有 | 京 ICP 备 XXXXXXXX 号