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

洛谷 P8512

有长度为 \(m\) 的序列 \(a\)(初始全为 \(0\))以及 \(n\) 次操作,每次操作形如 \(l, r, v\),表示将 \(a_{l} \sim a_r\) 变为 \(v\)。现在给定 \(q\) 组询问,每组询问给定 \(l, r\),输出若依次执行第 \(l \sim r\) 次操作后 \(a\) 之和为多少?

先考虑执行全部的操作,使用 ODT 可以在 \(O(n \log n)\) 的时间内完成并且知道有都少个数为 \(v\)。那么这个题离线下来将操作按 \(r\) 排序,边枚举询问边做 ODT 即可。

而对于 \(l\),询问有多少个数的颜色还是第 \(1 \sim l - 1\) 次操作留下的,做 ODT 时树状数组维护即可。

时间复杂度:\(O((n + q) \log n)\)

没啥思维量。

http://www.hskmm.com/?act=detail&tid=33270

相关文章:

  • 从libtorch_cuda.so中提取某个函数的sass汇编指令
  • 【题解】成外友谊赛
  • 小程序商城客服系统
  • ubuntu 主机创建虚拟 ip,应对容器内部配置了宿主固定 ip,宿主迁移网络环境后容器报错
  • 2025权威报告:微信编辑器排版Top 10工具推荐(全链路解决方案)
  • 洛谷 P10149
  • 从0到1构建企业数据资产 - 智慧园区
  • 2025.10.17
  • 一行代码清空所有 docker 容器的日志文件
  • 塔吊施工 “隐形风险” 克星!思通数科 AI 卫士精准识别核心部件隐患
  • ubuntu配置vsftpd
  • 时序数据库 Apache IoTDB 等你“打卡”!2025 OSCAR 开源产业大会完整版议程揭晓
  • 2024 CCPC Final F
  • vue
  • Windows关闭端口占用
  • 洛谷 P12865
  • ubuntu清理内存缓存
  • ubuntu常用技巧
  • 10.17 CSP-S模拟33 改题记录
  • 包装类(基本数据类型对应的引用数据类型)
  • luogu P7915 [CSP-S 2021] 回文
  • USACO 绿-蓝 思维题小记
  • Day16-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\classlei
  • 一个实用的短视频脚本创作指令分享
  • 字典树 Trie 乱讲
  • redis和mysql之间的数据一致性
  • ubuntu允许root登录桌面系统
  • 24. 两两交换链表中的节点
  • AI协科学家:技术革命还是安全噩梦?
  • 一个决定