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

CF2146E

对于数组 \(a\),定义 \(w(a)\)\(a\) 中满足 \(a_i > mex(a)\) 的下标数。现在给定长度为 \(n\) 的数组,对于每个 \(r\), 求出 \(\max\limits_{l = 1}^{r} w(a[l \sim r])\)

考虑枚举 \(x = mex(a)\),设 \(x\) 出现的位置是 \(p_1 < p_2 < \cdots < p_k\)。对于 \(r = p_i\) 是没有贡献的,对于 \(p_i < r < p_{i + 1}\) 的贡献是 \(a_{p_i + 1} \sim a_r\)\(> x\) 的数量(取 \(l = p_i + 1\))。

但是这有个问题,不能保证 \(x\)\(a_{l} \sim a_r\)\(mex\)。但没有关系,因为这个 \(mex\) 一定小于等于 \(x\),且真正的 \(mex\)\(r\) 的贡献肯定不劣于 \(x\)\(r\) 的贡献(\(> mex\) 的数更多)。

\(b_i\) 表示 \(i = mex\) 对当前 \(r\) 的贡献。从左往右扫一遍 \(r\),有一下三种情况:

  • \(a_r = i\)\(b_i \leftarrow 0\)
  • \(a_r > i, b_i \leftarrow b_i + 1\)
  • \(a_r < i\)\(b_i\) 不变。

现在问题就转化为了一个区间加与单点赋值的问题,使用线段树轻松解决。

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

此题关键是想到枚举 \(mex\),考虑 \(mex\)\(r\) 的贡献,然后进行扫描线即可。(没想到扫描线纯 sb

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

相关文章:

  • Spring Boot项目中集成Spring Security OAuth2和Apache Shiro
  • 【博客导航】
  • 部署向量数据库milvus
  • 从 0 到 1 实现高性能日志库 MiniSpdlog — 这可能是最适合新手的日志系统实战项目 !
  • 思想惰性:警惕时代中的精神惯性
  • journalctl 查看服务日志
  • 对ssh修改源码过程
  • 低代码时代,企业机遇在哪里
  • 2025 年浙江专升本培训学校推荐榜:浙江/台州/萧山/温州专升本机构,聚焦学历提升需求,杭州泓涵培训学校为学子护航
  • 25noip20d2t2 马戏表演 - Slayer
  • 从后端转行为AI工程师,转行AI大模型开发,附全套学习资源!收藏这份指南! - 实践
  • 实验一:现代C++初体验
  • 2025秋_11
  • 软件工程学习日志2025.10.14
  • CF1784E
  • nSwitch 存档自动备份系统模块 - autoSAVE
  • java基础7-字符串
  • 乐云具身活动体验
  • 【技术解决方案】联邦学习中遇到的Non-IID问题——隐语SecretFlow
  • 学习笔记:KTT
  • 题解:P10104 [GDKOI2023 提高组] 异或图
  • 2025 年筛网厂家推荐榜:聚焦场景适配与高效需求,锰钢筛网/聚氨酯筛网/合金焊接筛网/自清洁筛网/防堵筛网厂家滨州沃森网业成优选
  • P7076 [CSP-S2020] 动物园
  • 汽车价格战全面熄火了?不卷价格该卷什么? - 教程
  • P10067 [CCO 2023] Real Mountains
  • 先辈题解
  • U-Boot启动探秘:从汇编到命令行的奇幻之旅 - 指南
  • 双指针的初步了解
  • 倍增并查集学习笔记
  • 两数相加-leetcode